Keshawn_lu's Blog

Leetcode 剑指 Offer 11. 旋转数组的最小数字

字数统计: 394阅读时长: 1 min
2020/07/22 Share

题目简介:

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2][1,2,3,4,5] 的一个旋转,该数组的最小值为1。

示例 1:

1
2
输入:[3,4,5,1,2]
输出:1

示例 2:

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

思路:

摸鱼做法:直接sort,返回数组最小值即可。

二分做法:设最小值在数组的下标为min,将每次的numbers[mid]numbers[right]比较,存在三种情况:

  1. numbers[mid] < numbers[right],此时mid位于[min, right),所以将right = mid

  2. numbers[mid] > numbers[right],此时mid位于[left, min),所以将left = mid + 1

  3. numbers[mid] = numbers[right],此时无法判别mid位于最小值的左侧还是右侧,就像下面这个例子一样,numbers[mid] = numbers[right] = 1。所以将right--,缩小范围。

    1
    [1, 1, 1, 0, 1, 1, 1]

最后返回numbers[left]即可。

tip:

  • numbers[right]作比较的原因通过与它的比较,能得出numbers[mid]在最小值的左侧还是右侧,而numbers[left]则不行。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int minArray(vector<int>& numbers) {

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

while(left <= right){

int mid = (right - left) / 2 + left;

//mid在最小值左侧
if(numbers[mid] > numbers[right])
left = mid + 1;

//mid在最小值右侧
else if(numbers[mid] < numbers[right])
right = mid;

//无法判断mid在左侧还是右侧
else
right--;
}

return numbers[left];
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: