33. 搜索旋转排序数组

  1. class Solution {
  2. public:
  3.     int searchNum(vector<int>& nums, int ll, int rr, int target){
  4.         int l = ll, r = rr;
  5.         //搜索左边的边界点，题目会出现没有旋转的情况【1】，【1，3】
  6.         //这种情况你利用num[mid] < mus[0]找右边界点会有问题
  7.         while(l < r){
  8.             int mid = l + r >> 1;
  9.             if(nums[mid] >= target) r = mid;
  10.             else l = mid + 1;
  11.         }
  12.         return nums[r] == target ? r : -1;
  13.     }
  14.     int search(vector<int>& nums, int target) {
  15.         int l = 0, r = nums.size() - 1;
  16.         while(l < r){
  17.             int mid = l + r + 1 >> 1;
  18.             if(nums[mid] >= nums[0]) l = mid;
  19.             else r = mid - 1;
  20.         }
  21.         if(target >= nums[0]){
  22.             return searchNum(nums, 0, l, target);
  23.         }else{
  24.             return searchNum(nums, l+1, nums.size() - 1, target);
  25.         }
  26.     }
  27. };

81. 搜索旋转排序数组 II

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.empty()) return false;
        int R = nums.size() - 1;
        //1. 针对全是一样的情况，【2，2，2，2】，留一个，继续执行后面的查找
        while(R > 0 && nums[R] == nums[0]) R--;
        //2. 针对全是一样的情况，一个不留，立即特判一下，不符合就不执行后面的了
        // while (R >= 0 && nums[R] == nums[0]) R -- ;
        // if (R < 0) return nums[0] == target;

        int l = 0, r = R;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        if(target >= nums[0]) {r = l; l = 0;}
        else {l++; r = R;}

        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return nums[r] == target;
    }
};

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

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        if(nums[r] >= nums[0]) return nums[0];
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

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

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()) return false;
        int R = nums.size() - 1;
        //没有旋转
        if(nums[R] > nums[0]) return nums[0];
        //删除末尾和nums[0]一样的
        while(R >= 0 && nums[R] == nums[0]) R--;
        if(R < 0) return nums[0];

        int l = 0, r = R;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};
//【1，2，1】过不去
#------------------------------------------------------------------
class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()) return false;
        int R = nums.size() - 1;
        //删除末尾和nums[0]一样的
        //R > 0留一个数，应对只有一个数的情况【1】
        while(R > 0 && nums[R] == nums[0]) R--;
        //针对上面【1，2，1】的情况，下面返回的其实是第一个1，但是也计算出了答案
        //如果是找出旋转的下标，这样就不对了
        if(nums[R] > nums[0]) return nums[0];

        int l = 0, r = R;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return {-1,-1};
        int l = 0, r = nums.size() - 1;
        vector<int> res;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid+1;
        }
        if(nums[r] != target){return {-1,-1};}
        else{
            res.push_back(r);
            l = 0; r = nums.size() - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            res.push_back(r);
        }
        return res;
    }
};

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty()) return 0;
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        //【1，3，5】插入7，插入位置就要是最后一个下标+1了
        return nums[r] >= target ? r : r + 1;
    }
};
//把r设置为r = nums.size();就不用特判了，两种都可以，上面的好理解一点
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty()) return 0;
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

74. 搜索二维矩阵

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size(), n= matrix[0].size();
        int l = 0, r = m * n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(matrix[mid / n][mid % n] >= target) r = mid;
            else l = mid +1;
        }
        return matrix[r / n][r % n] == target;
    }
};

162. 寻找峰值

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] > nums[mid+1]) r = mid;
            else l = mid + 1;
        } 
        return r;
    }
};

274. H 指数

//这题和下面一题看的有点迷迷糊糊的，还要再看
class Solution {
public:
    int hIndex(vector<int>& c) {
        if(c.empty()) return 0;
        sort(c.begin(), c.end(), greater<int>());
        //[6,5,3,1,0]
        //h > 0 不是h >= 0是因为我们也要对【0，0，0】这样的数据判断
        for(int h = c.size(); h > 0; h--){
            //c[h-1]表示最小的数，如果最小的数都大于等于h
            //那就证明数组中一定有h个数大于等于h
            //我们要找的就是就是这个h
            if(c[h-1] >= h) return h;
        }
        return 0;
    }
};
//------------------------------------
//正向排序与下面的题结合起来
class Solution {
public:
    int hIndex(vector<int>& c) {
        if(c.empty()) return 0;
        sort(c.begin(), c.end());
        int n = c.size();
        if(c[n - 1] == 0) return 0;
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(c[mid] >= n-mid) r = mid;
            else l = mid + 1;
        }
        return n - r;
    }
};

275. H 指数 II

//上一题因为要排序，已经是nlogn了，没有必要在二分了
//现在排好序了，就可以降到logn了
class Solution {
public:
    int hIndex(vector<int>& c) {
        int n = c.size();
        int l = 0, r = n;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(c[n-mid] >= mid) l = mid;
            else r = mid - 1;
        }
        return r;
    }
};
//---------------------------------------
//这个逻辑更好理解一点https://www.acwing.com/solution/content/2806/
class Solution {
public:
    int hIndex(vector<int>& c) {
        int n = c.size();
        if(n == 0 || c[n - 1] == 0) return 0;
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(c[mid] >= n-mid) r = mid;
            else l = mid + 1;
        }
        return n - r;
    }
};

278. 第一个错误的版本

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 0, r = n;
        while(l < r){
            //2126753390
            //1702766719 可能会有溢出，要转换一下
            int mid = (long)l + r >> 1;
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

436. 寻找右区间

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& q) {
        //一共有多少个区间
        int n = q.size();
        //把每个区间的下标，放在每个区间的最后
        for(int i = 0; i < n; i++) q[i].push_back(i);
        //把所有区间排序
        sort(q.begin(), q.end());
        //结果，如果没有找到，结果就是-1，找到了后面会覆盖
        vector<int> res(n, -1);
        //枚举每个区间
        for(auto& x: q){
            int l = 0, r = n - 1;
            while(l < r){
                int mid = l + r >> 1;
                //mid的左端点，大于等于当前区间的又端点
                if(q[mid][0] >= x[1]) r = mid;
                else l = mid + 1;
            }
            //判断找到的那个区间是否符合条件
            if(q[r][0] >= x[1]){
                //当前下标的值等于找到的区间的下标值
                res[x[2]] = q[r][2];
            }
        }
        return res;
    }
};