Haiyang Yu's Blog
0%

发表于 更新于 Valine：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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

1.一次失败的尝试

这题思路很简单, 就是求出mid之后然后和两端元素比较, 判断最小值在mid左边还是右边.

重点是处理重复的元素. 如果numbers[mid] == numbers[begin]或numbers[end]会怎样.

我一开始是同时用了三个元素来判断, numbers[mid], numbers[begin], numbers[end]

  • 如果numbers[begin] == numbers[mid], 就将begin右移直到不等于numbers[mid]

  • 如果numbers[end] == numbers[mid], 就将end左移直到不等于numbers[mid]

  • 如果numbers[mid] > numbers[begin] 就说明最小值在mid到end中

  • 如果numbers[mid] < numbers[end]就说明最小值在begin到mid中.

后来发现这三个元素是不必要的. 只需要判断numbers[mid], numbers[end]即可. 因为比numbers[end]大并且比numbers[begin]小的元素是不存在的. 只要比numbers[end]大就可以说明最小值在mid到end中了.

而且, 如果碰到了numbers[end] == numbers[mid]的情况, 只需要end左移一次就好, 下一次迭代重新计算mid和end就好, 不用一直移动end直到numbers[end] != numbers[mid]. 时间上不会有任何提升而且会使得逻辑错误.

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
28
29
30
31
32
33
34
35
36
37
//失败代码, 最后被numbers[mid] == numbers[end]和numbers[mid] == numbers[begin]这种情况搞得一团糟
//并且会得到错误的解! 反例[10,1,10,10,10]
//第一次有begin = 0, mid = 2, end = 4
//然后因为numbers[mid] == numbers[end]和numbers[mid] == numbers[begin]不断地右移begin和左移end
//得到begin = 1, mid = 2, end = 2
//然后因为有判断numbers[mid] > numbers[begin]成立, 进入mid到end中查找最小值, 得到10. 但是事实上错过了最小值1
class Solution {
    public int minArray(int[] numbers) {
        if(numbers == null || numbers.length == 0)
            throw new RuntimeException("InvalidInputException");
        int begin = 0;
        int end = numbers.length - 1;
        if(numbers[end] > numbers[begin])
            return numbers[begin];
        while(begin < end)
        {
            int mid = begin + (end - begin) / 2;
            while(numbers[mid] == numbers[begin] && begin < mid)
            {
                ++begin;
            }
            while(numbers[mid] == numbers[end] && end > mid)
            {
                --end;
            }
            if(numbers[mid] > numbers[begin])
            {
                begin = mid;
            }
            else if(numbers[mid] < numbers[end])
            {
                end = mid;
            }
        }
        return Math.min(numbers[begin], numbers[end]);
    }
}

2. 正确解法

只需要判断numbers[mid], numbers[end]即可. 因为比numbers[end]大并且比numbers[begin]小的元素是不存在的. 只要比numbers[end]大就可以说明最小值在mid到end中了.

而且, 如果碰到了numbers[end] == numbers[mid]的情况, 只需要end左移一次就好, 下一次迭代重新计算mid和end就好, 不用一直移动end直到numbers[end] != numbers[mid]. 时间上不会有任何提升而且会使得逻辑错误.

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
class Solution {
    public int minArray(int[] numbers) {
        if(numbers == null || numbers.length == 0)
            throw new RuntimeException("InvalidInputException");
        int begin = 0;
        int end = numbers.length - 1;
        if(numbers[end] > numbers[begin])
            return numbers[begin];
        while(begin < end)
        {
            int mid = begin + (end - begin) / 2;
            if(numbers[mid] > numbers[end])
            {
                begin = mid + 1;
            }
            else if(numbers[mid] < numbers[end])
            {
                end = mid;
            }
            else{
                --end;
            }
        }
        return numbers[begin];
    }
}