11（154） 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

示例 1：

输入：numbers = [3,4,5,1,2]
输出：1

示例 2：

输入：numbers = [2,2,2,0,1]
输出：0

提示：

  • n == numbers.length
  • 1 <= n <= 5000
  • -5000 <= numbers[i] <= 5000
  • numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

题解

class Solution {
public:
    int minArray(vector<int>& numbers) {
int i = 0, j = numbers.size() - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];


    }
};

53 - I 在排序数组中查找数字

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

题解

class Solution {
public:
    int helper(vector<int>& nums, int tar)
    {
        int i = 0, j = nums.size() - 1;
        while(i<=j){
            int m = (i+j)/2;
            if(nums[m]<=tar)i=m+1;
            else j = m-1;
        }
        return i;
    }
    int search(vector<int>& nums, int target) {
        return helper(nums, target) - helper(nums, target -1);
    }
};

53 - II 0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：

1 <= 数组长度 <= 10000

题解

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i = 0, j = nums.size()-1;
        while(i<=j){
            int m = (i+j)/2;
            if(nums[m]==m) i=m+1;
            else j=m-1;
        }
        return i;
    }
};

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

题解

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        return {searchLeftOrRightBound(nums,target,"left"),searchLeftOrRightBound(nums,target,"right")};
    }
private:
    int searchLeftOrRightBound(vector<int>& nums, int target, const string& bound)
    {
        int left = 0, right = nums.size() - 1;
        int res = -1;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid]>target){
                right = mid-1;
            }
            else{
                res = mid;
                if(bound == "left"){
                    right = mid - 1;
                }
                else if(bound == "right"){
                    left = mid + 1;
                }
                else{

                }
            }
        }
        return res;
    }
};