找到需要补充粉笔的学生编号(约瑟夫环+前缀和+二分)

x33g5p2x  于10个月前 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(118)

在这里插入图片描述

在这里插入图片描述

约瑟夫环:

时间复杂度:O(n)
空间复杂度:O(1)

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {

        int n=chalk.size(),i=-1;
        long long sum=0;
        for(int j=0;j<n;j++)
            sum+=chalk[j];
        k%=sum;
        while(1){
            i=(i+1)%n;
            if(k<chalk[i]){
                return i;
            }else{
                k-=chalk[i];
            }
        }
        
        return 0;
    }
};

前缀和+二分:

时间复杂度:O(n)
空间复杂度:O(1)

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {

        int n=chalk.size();
        if(chalk[0]>k){
            return 0;
        }
        
        //求前缀和
        for(int i=1;i<n;i++){
            chalk[i]+=chalk[i-1];
            if(chalk[i]>k){
                return i;
            }
        }

        k%=chalk[n-1];

        //二分查找
        int i=0,j=n-1;
        while(i<=j){
            int mid=(i+j)/2;
            if(chalk[mid]>k){
                j=mid-1;
            }else if(chalk[mid]<=k){
                i=mid+1;
            }
        }
        return i;
       // return upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin();
    }
};

相关文章