Find Minimum in Rotated Sorted Array II

Question

Problem Statement

Suppose a sorted array 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.

The array may contain duplicates.

Example

Given [4,4,5,6,7,0,1,2] return 0

题解

由于此题输入可能有重复元素，因此在num[mid] == num[end]时无法使用二分的方法缩小start或者end的取值范围。此时只能使用递增start/递减end逐步缩小范围。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param num: a rotated sorted array
  5.      * @return: the minimum number in the array
  6.      */
  7.     int findMin(vector<int> &num) {
  8.         if (num.empty()) {
  9.             return -1;
  10.         }
  12.         vector<int>::size_type start = 0;
  13.         vector<int>::size_type end = num.size() - 1;
  14.         vector<int>::size_type mid;
  15.         while (start + 1 < end) {
  16.             mid = start + (end - start) / 2;
  17.             if (num[mid] > num[end]) {
  18.                 start = mid;
  19.             } else if (num[mid] < num[end]) {
  20.                 end = mid;
  21.             } else {
  22.                 --end;
  23.             }
  24.         }
  26.         if (num[start] < num[end]) {
  27.             return num[start];
  28.         } else {
  29.             return num[end];
  30.         }
  31.     }
  32. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param num: a rotated sorted array
  4.      * @return: the minimum number in the array
  5.      */
  6.     public int findMin(int[] num) {
  7.         if (num == null || num.length == 0) return Integer.MIN_VALUE;
  9.         int lb = 0, ub = num.length - 1;
  10.         // case1: num[0] < num[num.length - 1]
  11.         // if (num[lb] < num[ub]) return num[lb];
  13.         // case2: num[0] > num[num.length - 1] or num[0] < num[num.length - 1]
  14.         while (lb + 1 < ub) {
  15.             int mid = lb + (ub - lb) / 2;
  16.             if (num[mid] < num[ub]) {
  17.                 ub = mid;
  18.             } else if (num[mid] > num[ub]){
  19.                 lb = mid;
  20.             } else {
  21.                 ub--;
  22.             }
  23.         }
  25.         return Math.min(num[lb], num[ub]);
  26.     }
  27. }

源码分析

注意num[mid] > num[ub]时应递减 ub 或者递增 lb.

复杂度分析

最坏情况下 O(n), 平均情况下 O(\log n).