TwoPoints

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/20/]

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

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为0，请返回-1。

样例

1
2
3
输入：nums=[2,2,2,0,1]

输出：0

算法描述

  • 特殊情况特殊处理，长度为0、旋转的元素为0个,长度为0直接返回-1，没有旋转返回nums[0]
  • 去掉后面因为旋转可能与nums[0]相等的值，整个数组可以看作递增，可以二分思想解题
    • 在满足newNums[0]>newNums[mid]条件下，r=mid
    • 否则l=mid+1
  • 返回结果newNums[r]

C++代码

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

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        if(n==0)return -1;
        if(nums[0]<nums[n-1])return nums[0];
        while(n>0&&nums[0]==nums[n-1])n--;
        int[] newNums = Arrays.copyOf(nums,n);
        // System.out.println(Arrays.toString(newNums));
        int l=0,r=newNums.length-1;
        while(r>l){
            int mid = r+l>>1;
            if(newNums[0]>newNums[mid])r=mid;
            else l=mid+1;
        }
        return newNums[r];
    }
}