1894-找到需要补充粉笔的学生编号

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1
的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i
的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充
粉笔。

请你返回需要 补充 粉笔的学生 编号 。

示例 1：

**输入：** chalk = [5,1,5], k = 22
**输出：** 0
**解释：** 学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。

示例 2：

**输入：** chalk = [3,4,1,2], k = 25
**输出：** 1
**解释：** 学生消耗粉笔情况如下：
- 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。
编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。

提示：

  • chalk.length == n
  • 1 <= n <= 105
  • 1 <= chalk[i] <= 105
  • 1 <= k <= 109

方法一：优化的模拟

思路与算法

学生消耗粉笔的过程是重复的。记每一轮消耗粉笔的总量为 total，它等于数组 chalk 的元素之和。因此，我们可以将粉笔数量 k 对 total 进行取模，求得余数 k’ 以方便后续计算。由于 k’ 一定小于 total，因此我们只需要至多遍历一遍数组 chalk，同时模拟 k’ 减小的过程，即可以得到需要补充粉笔的学生编号。

细节

由于 total 可能会超过 32 位有符号整数的范围，因此对于一些整数类型有范围的语言，为了避免溢出，需要使用 64 位整数存储 total。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        int n = chalk.size();
        long long total = accumulate(chalk.begin(), chalk.end(), 0LL);
        k %= total;
        int res = -1;
        for (int i = 0; i < n; ++i) {
            if (chalk[i] > k) {
                res = i;
                break;
            }
            k -= chalk[i];
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long total = 0;
        for (int num : chalk) {
            total += num;
        }
        k %= total;
        int res = -1;
        for (int i = 0; i < n; ++i) {
            if (chalk[i] > k) {
                res = i;
                break;
            }
            k -= chalk[i];
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int ChalkReplacer(int[] chalk, int k) {
        int n = chalk.Length;
        long total = 0;
        foreach (int num in chalk) {
            total += num;
        }
        if (k >= total) {
            k %= (int) total;
        }
        int res = -1;
        for (int i = 0; i < n; ++i) {
            if (chalk[i] > k) {
                res = i;
                break;
            }
            k -= chalk[i];
        }
        return res;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        total = sum(chalk)
        k %= total
        res = -1
        for i, cnt in enumerate(chalk):
            if cnt > k:
                res = i
                break
            k -= cnt
        return res
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var chalkReplacer = function(chalk, k) {
    const n = chalk.length;
    let total = 0;
    for (const num of chalk) {
        total += num;
    }
    k %= total;
    let res = -1;
    for (let i = 0; i < n; ++i) {
        if (chalk[i] > k) {
            res = i;
            break;
        }
        k -= chalk[i];
    }
    return res;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func chalkReplacer(chalk []int, k int) int {
    total := 0
    for _, v := range chalk {
        total += v
    }
    k %= total
    for i, c := range chalk {
        if k < c {
            return i
        }
        k -= c
    }
    return 0
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 chalk 的长度。我们最多遍历数组 chalk 两次，第一次求出粉笔的总量 total，第二次找出答案。

  • 空间复杂度：O(1)。

方法二：前缀和 + 二分查找

思路与算法

对于方法一中的第二次遍历，我们也可以使用二分查找进行加速。

在对数组 chalk 的遍历过程中，我们可以求出其前缀和，记为数组 pre。那么需要补充粉笔的学生编号 i’ 是最小的满足 pre}[i] > k’ 的下标 i’，可以通过二分查找在 O(\log n) 的时间内找出。

细节

由于前缀和数组中的元素可能会超过 32 位整数的范围，因此不能直接在原数组上计算并更新前缀和。但可以注意到的是，本题中 k \leq 10^9，因此在计算前缀和数组的过程中，如果超过了 k，说明我们找到了需要补充粉笔的学生编号，此时就无需继续计算下去，那么也就不会超过 32 位整数的范围了。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.back();
        return upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin();
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        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];
        return binarySearch(chalk, k);
    }

    public int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
    public int ChalkReplacer(int[] chalk, int k) {
        int n = chalk.Length;
        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];
        return BinarySearch(chalk, k);
    }

    public int BinarySearch(int[] arr, int target) {
        int low = 0, high = arr.Length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        n = len(chalk)
        if chalk[0] > k:
            return 0
        for i in range(1, n):
            chalk[i] += chalk[i - 1]
            if chalk[i] > k:
                return i

        k %= chalk[-1]
        return bisect_right(chalk, k)
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var chalkReplacer = function(chalk, k) {
   const n = chalk.length;
    if (chalk[0] > k) {
        return 0;
    }
    for (let i = 1; i < n; ++i) {
        chalk[i] += chalk[i - 1];
        if (chalk[i] > k) {
            return i;
        }
    }

    k %= chalk[n - 1];
    return binarySearch(chalk, k);
};

const binarySearch = (arr, target) => {
    let low = 0, high = arr.length - 1;
    while (low < high) {
        const mid = Math.floor((high - low) / 2) + low;
        if (arr[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func chalkReplacer(chalk []int, k int) int {
    if chalk[0] > k {
        return 0
    }
    n := len(chalk)
    for i := 1; i < n; i++ {
        chalk[i] += chalk[i-1]
        if chalk[i] > k {
            return i
        }
    }
    k %= chalk[n-1]
    return sort.SearchInts(chalk, k+1)
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 chalk 的长度。计算前缀和的时间复杂度为 O(n)，二分查找的时间复杂度为 O(\log n)，因此总时间复杂度为 O(n)。

  • 空间复杂度：O(1)。

 Comments
On this page
1894-找到需要补充粉笔的学生编号