博客

[Leetcode 153]

• Question
  
  Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

  (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

  Find the minimum element.

  You may assume no duplicate exists in the array.

• 思路
  
  这个题是《剑指offer》中非常经典的一道题。
  
  对于没有重复数字的数组， 旋转之后的数组可以看做两个升序数组，而且前面数组的元素都比后面数组元素大。可以用二分查找。
  
  代码如下：

  int findMin(vector<int> &num) {
      int left= 0;
      int right = num.size() - 1;
      int mid = 0;
  
      while(left < right) {
          mid = (left + right) / 2;
          //nums[mid] >nums[right]  说明nums[mid] 属于前面的数组
          if (num[mid] > num[right]) {
              left = mid + 1;   //可以加1，将查找范围往后推
          }
          else if (num[mid] < num[right]) {
              right = mid;    //不可以减1, 因为mid可能就是我们要查找的元素
          }
  
      }
      return num[left];
  }

• letecode 154 在153的基础上加了一点， 那就是 查找的数组中包含了重复数字。 这上面代码只能处理nums[mid] == nums[right]，对于 nums[mid]==nums[left] 或者 的情况无法处理。
  
  例如：[10,1,10,10,10]， 就没法得出结果。《剑指offer》中遇到 nums[left]=nums[mid] == nums[right]这种情况就对数组[left,right] 内的元素进行顺序遍历。但是我在网上发现了一个更棒的方法（详见
  
  这里
  
  ）
  
  他在遇到 nums[mid] == nums[right]的情况， 就让–right; 避开相等情况，同时也不会影响查找最小数。因为当前的nums[right]是最小数，–right去掉之后，因为有与nums[right]相等的元素任然在查找范围内，所以不会影响最后结果。
  
  代码如下：

  int findMin(vector<int> &num) {
      int left= 0;
      int right = num.size() - 1;
      int mid = 0;
  
      while(left < right) {
          mid = (left + right) / 2;
          //nums[mid] >nums[right]  说明nums[mid] 属于前面的数组
          if (num[mid] > num[right]) {
              left = mid + 1;   //可以加1，将查找范围往后推
          }
          else if (num[mid] < num[right]) {
           //不可以减1, 因为mid可能就是我们要查找的元素
              right = mid;   
          }
          else --right;  //处理相等情况。
  
      }
      return num[left];
  }