0%

剑指offer011 旋转数组的最小数字

Posted on In Valine:

Problem:

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

Intuition:

此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组，哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。那么对于初始情况来说，一个是非递减数组和一个旋转数组。其中最小的数肯定在旋转数组中，那么我们每次二分法都扔掉递增数组，只保留旋转数组。同时保证递增数组中最小的数字（也是第一个元素）被留下来。

通过修改二分查找算法进行求解（l 代表 low，m 代表 mid，h 代表 high）：

当 nums[m] <= nums[h] 时，表示 [m, h] 区间内的数组是非递减数组，[l, m] 区间内的数组是旋转数组，此时令 h = m；
否则 [m + 1, h] 区间内的数组是旋转数组，令 l = m + 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int minNumberInRotateArray(int[] nums) {
        if (nums.length == 0)
            return 0;
        int l = 0, h = nums.length - 1;
        while(l<h){
            int mid=(l+h)/2;
            //h=mid就是保留下了递增数组中最小的数字
            if(nums[mid]<=nums[h]){
                h=mid;
            }else{
                l=mid+1;
            }
        }
        return nums[l];
    }

做到上面这里核心思路也就完成了，面试官应该也比较满意了，但是解法中还有一点没有考虑到。如果数组元素允许重复，会出现一个特殊的情况：nums[l] == nums[m] == nums[h]，此时无法确定解在哪个区间，需要切换到顺序查找。例如对于数组 {1,1,1,0,1}，l、m 和 h 指向的数都为 1，此时无法知道最小数字 0 在哪个区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int minNumberInRotateArray(int[] nums) {
    if (nums.length == 0)
        return 0;
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[l] == nums[m] && nums[m] == nums[h])
            return minNumber(nums, l, h);
        else if (nums[m] <= nums[h])
            h = m;
        else
            l = m + 1;
    }
    return nums[l];
}

private int minNumber(int[] nums, int l, int h) {
    for (int i = l; i < h; i++)
        if (nums[i] > nums[i + 1])
            return nums[i + 1];
    return nums[l];
}