?前言?

开更五月集训专题，由浅入深，深入浅出，飞向大厂！

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
?联系方式：2201891280(QQ)
?全文大约阅读时间： 20min

全文目录

?前言?
35. 搜索插入位置
704. 二分查找
剑指 Offer 53 - I. 在排序数组中查找数字 I
911. 在线选举
写在最后

35. 搜索插入位置

解题思路

二分查找模板题

代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int right = nums.size(),left = 0;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] >= target)  right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

注意的点

没啥

704. 二分查找

解题思路

比上面的更进一步

代码

class Solution {
    int searchInsert(vector<int>& nums, int target) {
        int right = nums.size(),left = 0;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] >= target)  right = mid;
            else left = mid + 1;
        }
        return left;
    }
public:
    int search(vector<int>& nums, int target) {
        int ans = searchInsert(nums, target), n = nums.size();
        if(ans == n || nums[ans] != target) return -1;
        return ans;
    }
};

注意的点

没啥注意的、、

剑指 Offer 53 - I. 在排序数组中查找数字 I

解题思路

查找两次，看插入位置的差异就是重复次数。

代码

class Solution {
    int searchInsert(vector<int>& nums, int target) {
        int right = nums.size(),left = 0;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] >= target)  right = mid;
            else left = mid + 1;
        }
        return left;
    }
public:
    int search(vector<int>& nums, int target) {
        int left = searchInsert(nums, target), right = searchInsert(nums, target + 1);
        return right - left;
    }
};

注意的点

没有，这第一题被我当模板了。。。。

911. 在线选举

解题思路

根据每个时刻的获胜者统计出来，然后二分查找时刻就好了。

代码

class TopVotedCandidate {
    vector<int> selectcnt,winer,time;
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        int n = persons.size();
        selectcnt.resize(n,0),winer.resize(n,0),time.resize(n,0);    //全局变量初始化
        for(int i = 0;i < n;++i){
            ++selectcnt[persons[i]];
            time[i] = times[i];
            winer[i] = (i == 0 || selectcnt[persons[i]] >= selectcnt[winer[i -1]]) ? persons[i] : winer[i - 1];          
        }
    }
    
    int q(int t) {
        int l = 0, r = winer.size() - 1,ans = 0;
        while(l <= r){
            int mid = l + (r - l) /2;
            if(time[mid] > t)  r = mid - 1;
            else{
                ans = mid;
                l = mid + 1;
            }
        }
        return winer[ans];
    }
};