二分查找：其他

0315. 计算右侧小于当前元素的个数 (opens new window)

题目

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

解析

从后向前遍历原数组，通过二分插入排序维护一个有序数组，每次插入的下标即为右侧小于当前元素的数量。

注意

插入排序的最坏时间复杂度为 $O(n^2)$，当前已不能通过全部测试用例。

代码

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans(nums.size());
        vector<int> list;
        for (int i = nums.size() - 1; i >= 0; i --) {
            int idx = findIndex(list, nums[i]);
            ans[i] = idx;
            list.insert(list.begin() + idx, nums[i]);
        }
        return ans;
    }

    int findIndex(vector<int>& list, int target) {
        int left = 0;
        int right = list.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return min(left, (int)list.size());
    }
};

0354. 俄罗斯套娃信封问题 (opens new window)

题目

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

解析

将信封按宽度升序、高度降序，此时可将问题简化成 0300. 最长递增子序列，寻找到最长的高度递增序列即为结果。

代码

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) {
            return 0;
        }
        
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), cmp);
        
        vector<int> tails;
        tails.push_back(envelopes[0][1]);
        for (int i = 1; i < n; i ++) {
            if (envelopes[i][1] > tails.back()) {
                tails.push_back(envelopes[i][1]);
            } else {
                int l = 0, r = tails.size() - 1;
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (tails[mid] < envelopes[i][1]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                tails[l] = envelopes[i][1];
            }
        }
        return tails.size();
    }

    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
    }
};

0410. 分割数组的最大值 (opens new window)

题目

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

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

解析

由于结果只可能在数组最大值与数组和之间，以此作为边界进行二分法，每次划分条件为判断数组是否能完成指定的划分，最终时间复杂度为 $O(nlog(\rm{sum} - \rm{max}))$。

代码

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int maxNum = INT_MIN;
        long total = 0;
        for (int i = 0; i < nums.size(); i ++) {
            maxNum = max(maxNum, nums[i]);
            total += nums[i];
        }
        long left = maxNum;
        long right = total;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (_valid(nums, mid, m)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    bool _valid(const vector<int>& nums, long target, int m) {
        long sum = 0;
        int cnt = 1;
        for (int i = 0; i < nums.size(); i ++) {
            sum += nums[i];
            if (sum > target) {
                sum = nums[i];
                cnt ++;
            }
            if (cnt > m) {
                return false;
            }
        }
        return true;
    }
};

0497. 非重叠矩形中的随机点 (opens new window)

题目

给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。

提示：

• 整数点是具有整数坐标的点。
• 矩形周边上的点包含在矩形覆盖的空间中。
• 第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中 [x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
• 每个矩形的长度和宽度不超过 2000。
• 1 <= rects.length <= 100
• pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
• pick 最多被调用10000次。

解析

本题与 0528. 按权重随机选择 思路一致，只是需要额外存储矩形数据，同时前缀和的构建使用矩形中包含的点的个数。

代码

class Solution {
    vector<vector<int>> rects;
    vector<int> preSum;
public:
    Solution(vector<vector<int>>& rects) {
        this->rects = rects;
        int sum = 0;
        for (int i = 0; i < rects.size(); i ++) {
            sum += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
            preSum.push_back(sum);
        }
    }
    
    vector<int> pick() {
        vector<int> rect = rects[_pickIndex()];
        int x = rand() % (rect[2] - rect[0] + 1) + rect[0];
        int y = rand() % (rect[3] - rect[1] + 1) + rect[1];

        return vector<int>{x, y};
    }

    int _pickIndex() {
        int target = rand() % preSum.back() + 1;

        int left = 0;
        int right = preSum.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (preSum[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(rects);
 * vector<int> param_1 = obj->pick();
 */

0528. 按权重随机选择 (opens new window)

题目

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

解析

计算前缀和，将数组划分成多个区间，随机一个数字，落到哪个区间就将其划分至对应区域，可用二分法查找其对应区间。

代码

class Solution {
    vector<int> preSum;
public:
    Solution(vector<int>& w) {
        int sum = 0;
        for (int i = 0; i < w.size(); i ++){
            sum += w[i];
            preSum.push_back(sum);
        }
    }
    
    int pickIndex() {
        int target = rand() % preSum.back() + 1;

        int left = 0;
        int right = preSum.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (preSum[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */