题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

O(n)的复杂度,不够好,应该参考二分查找的实现.

public int minNumberInRotateArray(int[] array) {
    if (array == null || array.length == 0) {
        return 0;
    }
    for (int i = array.length - 1; i > 0; i--) {
        if (array[i - 1] > array[i]) {
            return array[i];
        }
    }
    return array[0];
}

改进版,要考虑到1,1,0,1,1,1,1等情况.

if (array == null || array.length == 0) {
    return 0;
}

int start = 0, end = array.length - 1;
int mid = (start + end) / 2;
/** 答案一定在start,mid,end的最大值和最小值之间 */
for (; array[start] >= array[end] && end - start >= 2; mid = (start + end) / 2) {//说明有接头处
    if (array[mid] < array[start] || array[mid] < array[end]) {
        end = mid;
    } else if (array[mid] > array[start] || array[mid] > array[end]) {
        start = mid;
    } else {//start,mid,end相等的特殊情况
        int min = Integer.MAX_VALUE;
        for (int i = start; i < end; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }
}

return Math.min(array[start], array[end]);

网上题解

链接：https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba?answerType=1&f=discussion
来源：牛客网

直接进行顺序的查找,复杂度为O(n).
但是我们看到题中是给出的有序的旋转数组,我们可以采用二分法来进行求解,其复杂度为O(logn).
这里我们需要利用带有条件的二分法来进行求解:

第一步我们可以将这个旋转的数组看作是前后两个有序的子数组,然后设定我们的中间值 mid = (start + end) // 2.

第二步我们能够看到,当我们选取的中间值 mid 所对应的值大于 start 所对应的值时,说明此时 mid 还在第一有序的数组中,而我们所要求解的最小值是在第二个有序数组的第一个位置,此时也就是在 mid 的后面,我们就将 start 移到 mid 所在的位置.

第三步,当我们的 end 所对应的值大于 mid 所对应的值时,说明最小值可能是 mid 所对应的值或者在 mid 的前面,我们将 end 移到 mid 所在的位置.

第四步,最后我们的 end 所在的位置就是最小值的位置,直接返回即可.

我说下,在牛客的这道题目中,以上的方法就可以提交完成,但是当我们看剑指offer的书时,有这样的特例比如数组 10111 , 这是会出现当 start mid end 所对应位置的值相等,这时候我们的程序就不能找到最小值,当出现这样的情况时,我们采用将 start 和 end 区间里面的值进行顺序查找来找出最小值.

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        if len(rotateArray) == 1:
            return rotateArray[0]
        start = 0
        end = len(rotateArray)-1

        while rotateArray[start] >= rotateArray[end]:
            if end - start == 1:
                break
            mid = (start + end) // 2
            if rotateArray[start] == rotateArray[mid] and rotateArray[end] == rotateArray[mid]:
                #进行顺序查找
                temp = rotateArray[start]
                for i in range(start,end + 1):
                    if temp < rotateArray[i]:
                        temp = rotateArray[i]
                return temp
            if rotateArray[mid] >= rotateArray[start]:
                start = mid
            elif rotateArray[end] >= rotateArray[mid]:
                end = mid
        return rotateArray[end]

Eric's Blogs

旋转数组的最小数字

题目描述

网上题解