欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【剑指offer】10.旋转数组的最小数字

程序员文章站 2022-06-17 19:54:06
...

【剑指offer】10.旋转数组的最小数字
LeetCode链接地址

直观解法并不难。从头到尾遍历数组,就能找到最小元素。但是时间复杂度是O(N),但是没有用到旋转数组的特性。

二分查找解法

注意到旋转之后的数组分为了两个有序的子数组。且前面的元素都大于或等于后面的子数组。而且最小值正好是两个子数组的分界线。考虑二分查找。

  1. 用两个指针分别指向数组的第一个元素和最后一个元素。(第一个元素应该大于等于最后一个元素)
  2. 然后寻找中间的元素。
  3. 如果该元素位于前面的子数组,它应该大于头指针,那么最小值应该位于它后面。可将头指针指向它
  4. 如果该元素位于后面的子数组,它应该小于头指针,那么最小值应该位于它前面。可将尾指针指向它
  5. 重复3 4
  6. 最后头指针应该指向前面子数组的最后,尾指针应该指向后面子数组的第一个。
  7. 返回尾指针

python

 def findMin(self, nums: List[int]) -> int:
        min_pos = 0
        max_pos = len(nums) - 1
        mid_pos = min_pos

        while(nums[min_pos]>nums[max_pos]):
            if max_pos - min_pos == 1:
                mid_pos = max_pos
                break
            mid_pos = ( min_pos + max_pos ) // 2
            if nums[mid_pos]>=nums[min_pos]:
                min_pos = mid_pos
            else:
                max_pos = mid_pos
        return nums[mid_pos

C++

 int findMin(vector<int>& nums) {
       int head = 0;
    int nail = nums.size()-1;
        int mid = head;
    while(nums[head]>nums[nail]){
        if(nail-head==1){
            mid = nail;
           break;
        }
        mid = (head+nail)/2;
        if(nums[mid]>nums[head]){
            head = mid;
        }
        else{
            nail = mid;
        }
      
    }
        return nums[mid];
    }