菜鸟笔记
提升您的技术认知

《剑指Offer》旋转数组的最小数字

阅读 : 405

题目描述:

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

解题思路:

  本题的直观解法很简单,直接对数组进行一次遍历就可以找到最小值,复杂度为O(n),但是显然这不是本题的意图所在,因为没有利用到任何旋转数组的特性。

  进一步分析,如果整个数组是有序的,那我们一定会想到用二分查找O(logn)来实现。对于旋转数组,我们发现,它实际上可以划分为两个排序的子数组,而且前面数组的元素都不小于后面数组的元素,并且最小值正好就是这两个数组的分界线,由此,我们可以得出以下解决方法。

  • 我们可以找到数组中间的元素。如果中间元素位于前面的递增子数组,那么它应该大于或者等于第一个指针指向的元素。此时最小元素应该位于该中间元素之后,然后我们把第一个指针指向该中间元素,移动之后第一个指针仍然位于前面的递增子数组中。

  • 同样,如果中间元素位于后面的递增子数组,那么它应该小于或者等于第二个指针指向的元素。此时最小元素应该位于该中间元素之前,然后我们把第二个指针指向该中间元素,移动之后第二个指针仍然位于后面的递增子数组中。

  • 第一个指针总是指向前面递增数组的元素,第二个指针总是指向后面递增数组的元素。最终它们会指向两个相邻的元素,而第二个指针指向的刚好是最小的元素,这就是循环结束的条件。

  首先用两个指针low和high分别指向数组的第一个元素和最后一个元素,然后可以找到中间元素mid。对于这个中间元素,有以下两种情况:(1)该元素大于等于low指向的元素,此时最小的元素说明在mid的后面,可以把low=mid;(2)中间元素小于等于high指向的元素,那么最小元素在mid之前,可以high=mid。特别注意:这里不要+1或者-1,因为只有这样才能保证low始终在第一个数组,high始终在第二个数组。依次循环,当最后low和high相差1时,low指向第一个数组的最后一个,high指向第二个数组的第一个(即为我们要找的最小值)。

  很明显,以上查找的时间复杂度为O(logN)。

旋转数组的最小数字

 除此之外,本题还有两个特殊情况:

  • 将数组前0个元素移动到后面(相当于没有旋转,数组整体有序)。明显我们上面的分析没有包含这种情况,需要特殊处理,方法也很简单,将第一个元素和最后一个元素相比,若第一个元素小于最后一个元素,则说明最小值就是的第一个元素,可以直接返回。

  • 首尾指针指向的数字和中间元素三者都相等时,无法判断中间元素位于哪个子数组,无法缩小问题规模。此时,只能退而求其次,进行顺序查找。

旋转数组的最小数字

代码实现(c++)

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int size = rotateArray.size();                            //数组长度
        if(size == 0){
            return 0;
        }
        int left = 0;                                            //左指针
        int right = size - 1;                                    //右指针
        int mid = 0;                                            //中间指针
        while(rotateArray[left] >= rotateArray[right]){            //确保旋转
            if(right - left == 1){                                //左右指针相邻
                mid = right;
                break;
            }
            mid = left + (right - left) / 2;                    //计算中间指针位置
            //特殊情况:如果无法确定中间元素是属于前面还是后面的递增子数组,只能顺序查找
            if(rotateArray[left] == rotateArray[right] && rotateArray[mid] == rotateArray[left]){
                return MinInOrder(rotateArray, left, right);
            }
            //中间元素位于前面的递增子数组,此时最小元素位于中间元素的后面
            if(rotateArray[mid] >= rotateArray[left]){
                left = mid;
            }
            //中间元素位于后面的递增子数组,此时最小元素位于中间元素的前面
            else{
                right = mid;
            }
        }
        return rotateArray[mid];
    }
private:
    //顺序寻找最小值
    int MinInOrder(vector<int> &num, int left, int right){
        int result = num[left];
        for(int i = left + 1; i < right; i++){
            if(num[i] < result){
                result = num[i];
            }
        }
        return result;
    }
};

代码实现(java)

public int minNumberInRotateArray(int [] array) {
        /*
        三种情况:
        (1)把前面0个元素搬到末尾,也就是排序数组本身,第一个就是最小值
        (2)一般情况二分查找,当high-low=1时,high就是最小值
        (3)如果首尾元素和中间元素都相等时,只能顺序查找
        */
        int len=array.length;
        if(len==0)
            return 0;
        int low=0,high=len-1;
        if(array[low]<array[high]) //排序数组本身
            return array[low];
        while(low<high){
            int mid=low+(high-low)/2;
            if(array[low]==array[mid] && array[high]==array[mid])
                return minInOrder(array);
            if(array[mid]>=array[low])
                low=mid;
            else if(array[mid]<=array[high])
                high=mid;
            if(high-low==1)
                return array[high];
        }
        return -1;
    }
    public int minInOrder(int [] array) { //顺序查找
         int min=array[0];
         for(int num:array){
             if(num<min)
                 min=num;
         }
          return min;
     }

代码实现(python2.7)

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        left = 0
        right = len(rotateArray) - 1
        mid = 0
        while rotateArray[left] >= rotateArray[right]:
            if right - left == 1:
                mid = right
                break
            mid = left + (right - left) // 2
            if rotateArray[left] == rotateArray[mid] and rotateArray[mid] == rotateArray[right]:
                return self.minInorder(rotateArray, left, right)
            if rotateArray[mid] >= rotateArray[left]:
                left = mid
            else:
                right = mid
        return rotateArray[mid]

    def minInorder(self, array, left, right):
        result = array[left]
        for i in range(left+1, right+1):
            if array[i] < result:
                result = array[i]
        return result

复杂度分析

  • 时间复杂度:O(logN) 。
  • 空间复杂度:O(1)。

笔记 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址