153. 寻找旋转排序数组中的最小值

image.png
注意为什么不用nums[mid]和nums[l]比较大小来识别最小值的位置，因为在[1,2,3,4]这个case下该策略就不管用了，所以比较点使用nums[r]。可以这样理解，排序数组[1,2,3,4,5,6]旋转后[4,5,6,1,2,3]，将数组分成了两个数组，前面一个数组[4,5,6]的元素都大于后面一个数组[1,2,3]的元素，要寻找的就是后面一个数组的第一个元素：

  • 当nums[mid]<nums[r]时，说明mid在后面一个数组中，此时r = mid;
  • 当nums[mid]>nums[r]时，说明mid在第一数组里，此时l = mid + 1

  • 当l==r时找到最小元素迭代结束

    1. class Solution {
    2.   public int findMin(int[] nums) {
    3.       if (nums == null || nums.length == 0) throw new IllegalArgumentException();
    4.       int l = 0, r = nums.length - 1;
    5.       while (l < r) {
    6.           int mid = l + (r - l) / 2;
    7.           if (nums[mid] > nums[r]) {
    8.               l = mid + 1;
    9.           } else {
    10.               r = mid;
    11.           } 
    12.       }
    13.       return nums[l];
    14.   }
    15. }

    154. 寻找旋转排序数组中的最小值 II

    image.png
    思路：和153题类似，主要考虑存在相等元素的情况，这里是个难点。

    class Solution {
  public int minArray(int[] numbers) {
      if(numbers == null || numbers.length == 0) throw new IllegalArgumentException();
      if (numbers[0] < numbers[numbers.length - 1]) return numbers[0];
      int l = 0, r = numbers.length - 1;
      while (l < r) {
          int mid = l + (r - l) / 2;
          if (numbers[mid] < numbers[r]) {
              r = mid;
          } else if (numbers[mid] > numbers[r]){
              l = mid + 1;
          } else {
              r = r - 1;
          }
      }
      return numbers[l];
  }
}

    300. 最长递增子序列

    方法1：动态规划
    方法2：贪心+二分查找

    33. 搜索旋转排序数组

    image.png

    
  class Solution {
      //[4,5,6,7,0,1,2],
      public int search(int[] nums, int target) {
          int minIndex = findMin(nums);
          if (minIndex == 0) {
              return binarySearch(nums, 0, nums.length - 1, target);
          }
          int left = binarySearch(nums, 0, minIndex - 1, target);
          int right = binarySearch(nums, minIndex, nums.length - 1, target);
          if (left == -1 && right == -1) return -1;
          return left == -1 ? right : left;
      }

      private int binarySearch(int[] nums, int l, int r, int target) {
          while (l <= r) {
              int mid = l + (r - l) / 2;
              if (nums[mid] < target) {
                  l = mid + 1;
              } else if (nums[mid] > target) {
                  r = mid - 1;
              } else {
                  return mid;
              }
          }
          return -1;
      }

      private int findMin(int[] nums) {
          int l = 0, r = nums.length - 1;
          while (l < r) {
              int mid = l + (r - l) / 2;
              if (nums[mid] > nums[r]) {
                  l = mid + 1;
              } else {
                  r = mid;
              }
          }
          return r;
      }
  }