LC.P1760[袋子里最少数目的球]

方法一：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1, right = (int) 1e9;
        while (left < right) {
            int mid = left + right >> 1;
            long s = 0;
            for (int x : nums) {
                s += (x - 1) / mid;
            }
            if (s <= maxOperations) right = mid;
            else left = mid + 1;
        }
        return right;
    }
}
  • 时间复杂度：$O(nlogC)$，其中在$C$为数组$nums$中的最大值
  • 空间复杂度：$O(1)$