LycTechStack

Lyc的个人成长技术栈

0%

【算法】二分查找

发表于 更新于 分类于
本文字数： 14k 阅读时长 ≈ 13 分钟

二分查找是一个常见的面试主题，也是计算机科学中最基本的算法思想之一，虽然二分查找比较简单，大部分专门考察二分查找的题目在实际机试中也几乎不会出现，但二分查找是许多困难题目中必不可少的一个步骤，因此值得单独花一定时间将其彻底掌握。这一节将学习三个不同的二分查找模板并在对应的题目上进行实践和巩固，这之中也不乏之前做过的题目，顺便复习一下。

1 模板 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size() - 1;
  while(left <= right){
    int mid = left + (right - left) / 2;
    if(nums[mid] == target) return mid;
    else if(nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
    
  return -1;
}

这是最标准的也是最简单的二分查找模板，是二分查找的最基本的形式，只要注意循环停止条件即可。

利用模板 #1 可以解决许多简单的二分查找问题：

x 的平方根

猜数字大小

搜索旋转排序数组：在不排序的情况下用二分查找，先判断左右两个区间哪个有序，因为分成两个区间一定有一个有序一个无序，我们在有序区间内很容易判断目标值是否在区间内，如果不在有序区间，那么目标值就在无序区间，再对另外的无序区间继续以上步骤，直到查找到目标值或跳出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) return mid;
            if(nums[mid] >= nums[0])    //左半部分有序
            {
                //如果目标值在该区间内，就在该区间查找
                if(target >= nums[0] && target < nums[mid]) right = mid - 1;
                //否则在另外一半区间查找
                else left = mid + 1;
            }
            else    //右半部分有序
            {
                if(target > nums[mid] && target <= nums[nums.size()-1]) left = mid + 1;
                else right = mid - 1;
            }
        } 
        return -1;
    }
};

2 模板 #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size();
  while(left < right){
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid; }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.size() && nums[left] == target) return left;
  return -1;
}

模板 #2 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件，因此循环结束条件是小于而不是小于等于，这样能保证区间中有至少两个元素，同时 right = mid 而不是 mid - 1 ，最后还要做后处理判断最后一个元素是否满足条件。

可以用这类模板的题目有：

第一个错误的版本：模板题

寻找峰值：实际上跟使用的模板无关，都可以做对，这道题关键在于能想到“一直往上爬总能到山顶”

寻找旋转排序数组中的最小值：因为本身就是要寻找最小值，所以必须是 right = mid，如果 right = mid - 1 可能会把最小值跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};

3 模板 #3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left + 1 < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

模板 #3 是二分查找的另一种独特形式。 它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。显然，和模板 #2 的区别是每次循环保证区间至少有三个元素，循环结束的条件是区间只剩两个元素。

可以用这类模板的题目有：

在排序数组中查找元素的第一个和最后一个位置：普通二分 + 中心扩展，但时间复杂度高于 O(logn) ；也可以两次二分，一次查找大于等于target的第一个下标，一次查找大于target的第一个下标，这样时间复杂度保证在 O(logn) ，在数组中 target 值很多的情况下显然两次二分更好。

找到 K 个最接近的元素：如果 x 在数组范围内，则二分查找先找到大于等于 x 的第一个下标，然后双指针从该下标开始向左右两边查找 k 次；如果 x 不在数组范围内则情况很简单。

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
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<int> ans;
        if(x < arr[0]) ans.assign(arr.begin(), arr.begin() + k);
        else if(x > arr[arr.size() - 1]) ans.assign(arr.end() - k, arr.end());
        else{	//在数组范围内则二分 + 双指针
            int left = 0, right = arr.size() - 1, t = 0;
            while(left <= right)	//先找到大于等于 x 的第一个下标
            {
                int mid = left + (right - left) / 2;
                if(arr[mid] >= x)
                {
                    t = mid;
                    right = mid - 1;
                }
                else left = mid + 1;
            }
            left = t - 1, right = t;
            for(int i = 0; i < k; ++i)		//开始向左右扩展寻找 k 次
            {
                if(left < 0)	//如果左指针已经到头了就直接向右扩展
                {
                    ++right;
                    continue;
                }
                else if(right > arr.size() - 1)		//同上，右指针到头直接向左扩展
                {
                    --left;
                    continue;
                }
                if(x - arr[left] <= arr[right] - x) --left;
                else ++right;
            }
            ans.assign(arr.begin() + left + 1, arr.begin() + right);
        }
        return ans;
    }
};

4 总结

二分查找最重要的是思想，一般在给定的数组是有序的情况下，一定可以用二分查找优化时间，上面的模板只是相对牵强的做一个总结，并不需要也不应该去记忆，只要能理解算法思想，实际题目中用什么样的二分查找，循环结束条件如何，怎样收缩区间，都要根据题目本身去确定。

5 更多练习

最接近的二叉搜索树值

给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。

注意：

  • 给定的目标值 target 是一个浮点数
  • 题目保证在该二叉搜索树中只会存在一个最接近目标值的数

二叉搜索树的中序遍历可以得到递增序列，因此最简单的方法就是中序遍历再查找，但是更高效的方法是直接判断目标值和当前节点的大小，如果比当前节点大说明最接近的值一定在当前节点的右子树，因此向右遍历，否则向左遍历，每次遍历记录最小差值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int ans = root->val;
        double minsub = DBL_MAX;
        while(root)
        {
            double sub = abs(target - root->val);
            if(sub <= minsub)
            {
                ans = root->val;
                minsub = sub;
            }
            root = (target >= root->val ? root->right : root->left);
        }
        return ans;
    }
};

搜索长度未知的有序数组

这是一个交互问题。

您有一个升序整数数组，其长度未知。您没有访问数组的权限，但是可以使用 ArrayReader 接口访问它。你可以调用 ArrayReader.get(i) 返回数组第 i 个索引**(0-indexed)**处的值(即secret[i])，如果 i 超出了数组的边界，则返回 INT_MAX

你也会得到一个整数 target，如果存在secret[k] == target，请返回索引 k 的值；否则返回 -1。

你必须写一个时间复杂度为 O(log n) 的算法。

关键在于确定二分边界，我们可以每次把边界扩大一倍，确定边界后就直接二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        int left = 0, right = 1;
        while(reader.get(right) < target)
        {
            left = right;
            right = right << 1;
        }
        while(left <= right)
        {
            int mid = left + ((right - left) >> 1);
            if(reader.get(mid) == target) return mid;
            if(reader.get(mid) > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};

Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

这是一道经典的问题，快速幂问题最好的做法就是分治，也算是二分的推广，我们每次计算 $x^{\frac{n}{2}}$，返回 $x^{\frac{n}{2}}$ 的平方，直到 $x^0 = 1$，这样就可以递归地快速算出答案，当然如果每次递归中 $n$ 是奇数，还需要额外乘一个 x，具体看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    double quickMul(double x, long long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

递归需要额外系统栈空间，因此最好改成迭代，关于迭代的推导可以查看官方题解，非常容易理解，将幂指数二进制分解，对应的二进制位是 1 就将结果乘到最终结果上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    double quickMul(double x, long long N) {
        double ans = 1.0;
        double x_contribute = x;
        while (N > 0) {
            if (N % 2 == 1) {
                ans *= x_contribute;
            }
            x_contribute *= x_contribute;
            N /= 2;
        }
        return ans;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

快速幂问题非常重要，之后还会遇到类似的问题。

有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

不要使用任何内置的库函数，如 sqrt 。

简单二分，可以看一下官方题解方法四的牛顿迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num < 2) return true;
        int l = 1, r = num >> 1;
        while(l <= r)
        {
            long mid = l + ((r - l) >> 1);
            long long s = mid * mid;
            if(s == num) return true;
            else if(s > num) r = mid - 1;
            else l = mid + 1;
        }
        return false;
    }
};

寻找比目标字母大的最小字母

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

  • 如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int l = 0, r = letters.size() - 1;
        char ans = letters[0];
        if(target == 'z') return ans;
        while(l <= r)
        {
            int m = l + (r -l) / 2;
            if(letters[m] > target)
            {
                ans = letters[m];
                r = m - 1;
            }
            else l = m + 1;
        }
        return ans;
    }
};

寻找旋转排序数组中的最小值 II

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并进行了多次旋转。请你找出并返回数组中的最小元素。你必须尽可能减少整个过程的操作步骤。

这是寻找旋转排序数组中最小值的进阶版，区别在于有重复元素，因此会存在特殊情况，就是重复的部分被旋转了，此时判断 nums[mid] 和 nums[right] 的关系可能存在二者相等的情况，这时整个数组的分布可能有下面两种情况：

1
2
3
    3
2 2     2 2 2 2 2
      1

这时最小值在左半区间，另一种情况：

1
2
3
        3
2 2 2 2     2 2 2
          1

这时最小值在右半区间，因此我们无法判断下一次在哪边区间查找，但无论哪种情况，我们只要不停收缩右边界，直到 nums[mid] != nums[right] 或者 right == mid ，最小值一定在区间内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int m = l + (r - l) / 2;
            if(nums[m] == nums[r]) --r;
            else if(nums[m] > nums[r]) l = m + 1;
            else r = m;
        }
        return nums[l];
    }
};

两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集 。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序 。

简单的排序 + 双指针问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int p1 = 0, p2 = 0;
        vector<int> ans;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        while(p1 < nums1.size() && p2 < nums2.size())
        {
            if(nums1[p1] == nums2[p2])
            {
                if(ans.empty() || ans.back() != nums1[p1]) ans.push_back(nums1[p1]);
                ++p1, ++p2;
            }
            else if(nums1[p1] > nums2[p2]) ++p2;
            else ++p1;
        }
        return ans;
    }
};

两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

同上，甚至更简单，无需重复判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        int p1 = 0, p2 = 0;
        vector<int> ans;
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        while(p1 < nums1.size() && p2 < nums2.size())
        {
            if(nums1[p1] == nums2[p2])
            {
                ans.push_back(nums1[p1]);
                ++p1, ++p2;
            }
            else if(nums1[p1] < nums2[p2]) ++p1;
            else ++p2;
        }
        return ans;
    }
};

两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案 ，而且你不可以重复使用相同的元素，并且你所设计的解决方案必须只使用常量级的额外空间。

之前在双指针部分做过，这道题自然双指针解法也更好，但也可以对于每一个数在它的右侧区间二分的进行查找，只是时间复杂度高于双指针法，因此也更推荐双指针做法。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size()-1;
        while(1)
        {
            if(numbers[left] + numbers[right] == target) return {left+1,right+1};
            else if(numbers[left] + numbers[right] < target) ++left;
            else --right;
        }
    }
};

6 用二分法解决困难题目

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回这个重复的数 。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

这道题看似不难，但其实是非常巧妙的一道题，值得反复琢磨。

首先看看为什么这道题没那么简单，第一，不允许修改数组使得我们不能对原数组排序；第二，必须使用 O(1) 额外空间使得我们也不能复制数组或者用哈希表，因此还是有一定难度的。

这道题很难想到用二分法，要想用二分法得基于一个很巧妙的性质：对于数组中的任何一个数 nums[i] ，如果用 cnt[i] 表示数组中小于等于 nums[i] 的数字的个数，那么如果 nums[i] 比重复数字 target 小，则一定满足 cnt[i] <= i ，反之如果 nums[i] 比重复数字 target 大，那么一定满足cnt[i] > i，这是一个一目了然的性质，但却很难想到。

因此我们可以二分的查找第一个满足 cnt[i] > i 的下标，即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                cnt += nums[i] <= mid;	//统计cnt[mid]
            }
            if (cnt > mid) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};

上面二分法的时间复杂度是 O(nlogn)，那能否在 O(n) 时间内完成呢？

回顾之前链表部分做过的环形链表问题，当时我们用到了快慢指针，慢指针每次走一步，快指针每次走两步，二者同时出发，如果链表有环，则快慢指针一定会相遇，相遇后慢指针回到起点，和快指针同时每次走一步前进，二者再次相遇处就是环的入口。

这道题完全可以利用快慢指针的思想，我们可以把整个数组建立一张图，数组中每个数字 x 指向 nums[x] ，这样一来如果有重复的数字 target，那么一定有两个或者多个 target 指向 nums[target]，此时相当于图中有环，我们利用快慢指针就可以找到环的入口，环的入口就是重复的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);
        slow = 0;
        while(slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

快慢指针的时间复杂度只有 O(n).

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度必须为 O(log (m+n)) 。

这是一道很经典的二分题目。因为规定了时间复杂度，因此不能使用合并+排序的方法，看到 log 也很容易想到二分，但是这道题即便是知道要用二分法也无从下手。

核心思想是：找到两个数组的中位数相当于找到两个数组中第 k 大的数，因此在两个数组中分别找到第 k / 2 大的数进行比较，较小的数所在的数组可以直接把前 k / 2 个数去掉，同时更新 k 的大小，这样每次就减小了一半的查找范围。

具体的细节和推导可以查看官方题解，代码中的细节也很多，这道题值得反复琢磨。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        int offset1 = 0, offset2 = 0;   //记录数组偏移
        while (true) {
            // 边界情况
            if (offset1 == m) { //数组 1 遍历完了，直接返回数组 2 第 k 大的数
                return nums2[offset2 + k - 1];
            }
            if (offset2 == n) { //同上
                return nums1[offset1 + k - 1];
            }
            if (k == 1) {   	//k为1则直接返回两个数组首元素最小值
                return min(nums1[offset1], nums2[offset2]);
            }

            // 正常情况
            int newIndex1 = min(offset1 + k / 2 - 1, m - 1);
            int newIndex2 = min(offset2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - offset1 + 1;
                offset1 = newIndex1 + 1;
            }
            else {
                k -= newIndex2 - offset2 + 1;
                offset2 = newIndex2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1) {
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        }
        else {
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
};

找出第 k 小的距离对

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

这也是一道比较困难的二分查找题目。第 k 小的距离一定在 [0, max(nums) - min(nums)] 之间，因此我们可以在这个区间上二分查找，然后统计 nums 中小于等于距离 mid 的数对的个数，如果小于等于距离 mid 的数对个数比 k 大，说明 mid 较大，在左区间查找，反之在右区间查找。注意这里的二分查找要用模板 #2，因为如果小于等于距离 mid 的数对个数比 k 大，第 k 个最小距离也可能就是 mid，因此右边界 right = mid。

至于如何统计 nums 中小于等于距离 mid 的数对的个数，最简单的方法可以暴力遍历，但是为了提高效率我们可以先对数组排序，然后双指针统计即可，具体方法见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    //返回距离比mid小的数对的个数
    int get(vector<int>&nums, int mid){
        int res = 0;
        for(int l = 0, r = 0; r < nums.size(); ++r){
            while(nums[r] - nums[l] > mid) l++;
            res += r - l;
        }
        return res;
    }
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0, r = *max_element(nums.begin(), nums.end()) - *min_element(nums.begin(), nums.end());
        while(l < r){
            int mid = l + r >> 1;
            if(get(nums, mid) >= k) r = mid;  //如果个数比k大，则说明mid比较大，在mid的左边寻找
            else l = mid + 1;                 //如果个数比k小，则说明mid比较小，在mid的右边寻找
        }
        return r;
    }
};

分割数组的最大值

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

这道题在动态规划中遇到过，但是用动态规划时空复杂度较高。最好的方法是二分 + 贪心，实际上思路和上一题很相似，我们可以确定答案的范围，然后通过二分查找去“猜”答案是什么。具体推导可以查看官方题解方法二。

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
31
32
33
34
35
class Solution {
public:
    bool check(vector<int>& nums, int x, int m) {
        long long sum = 0;
        int cnt = 1;
        for (int i = 0; i < nums.size(); i++) {
            if (sum + nums[i] > x) {
                cnt++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        return cnt <= m;
    }

    int splitArray(vector<int>& nums, int m) {
        long long left = 0, right = 0;
        for (int i = 0; i < nums.size(); i++) {
            right += nums[i];
            if (left < nums[i]) {
                left = nums[i];
            }
        }
        while (left < right) {
            long long mid = (left + right) >> 1;
            if (check(nums, mid, m)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
---- 本文结束 知识又增加了亿点点！----

文章版权声明 1、博客名称：LycTechStack
2、博客网址：https://lz328.github.io/LycTechStack.github.io/
3、本博客的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系博主进行删除处理。
4、本博客所有文章版权归博主所有，如需转载请标明出处。
相关文章