Find Minimum in Rotated Sorted Array II

2015.1.23 11:41

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.

Solution:

　　With duplicates in the array, it would be a little harder to perform binary search.

　　Consider the ocassion "1 ... 1 ... 1", with the left, right and middle elements being all "1", you don‘t know if the rotated pivot will lie in the left or right half of the sequence. If we scan the sequence at one end, removing all duplicates that are equal to the other end, it will make a legal sequence for binary search.

　　Here‘re some example data for my idea:

　　　　{1, 1, -1, 0, 1, 1, 1} -> remove {1, 1} on the right -> {1, 1, -1, 0}

　　　　{1, 1, 1, 2, 3} -> remove nothing -> {1, 1, 1, 2, 3}

　　　　{1, 1, 1, 1, 1} -> all equal to the left end are removed -> {1}

　　The next step would be a binary search, similar to the upper_bound() function in <algorithm>.

　　Total time complexity is on average O(log(n)), but O(n) in worst cases. Space complexity is O(1).

Accepted code:

 1 class Solution { 2 public: 3     int findMin(vector<int> &num) { 4         int n = (int)num.size(); 5          6         while (n > 1 && num[0] == num[n - 1]) { 7             --n; 8         } 9         10         if (n == 1 || num[0] < num[n - 1]) {11             return num[0];12         }13         14         int ll, mm, rr;15         16         ll = 0;17         rr = n - 1;18         while (rr - ll > 1) {19             mm = ll + (rr - ll) / 2;20             if (num[mm] >= num[ll]) {21                 ll = mm;22             } else {23                 rr = mm;24             }25         }26         27         return num[rr];28     }29 };

LeetCode - Find Minimum in Rotated Sorted Array II