LeetCode 154 - Find Minimum in Rotated Sorted Array II

Related - LeetCode 153 - Find the minimum element in a sorted and rotated array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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.

http://unknown66.blogspot.com/2016/03/leetcode-154-find-minimum-in-rotated.html

    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        
        while (low < high) {
            // mid == low if high - low < 2
            int mid = low + (high - low) / 2;
            
            // We can NOT compare mid with low because
            // it is possible mid == low and we can not
            // distinguish cases 1) mid == low or 2) nums[mid] == nums[low].
            // However, mid != high is always true.
            if (nums[mid] == nums[high]) high--; 
            else if (nums[mid] < nums[high]) high = mid; // nums[mid..high] is sorted
            else low = mid + 1;
        }
        
        return nums[low];
    }

http://www.cnblogs.com/zuoyuan/p/4045758.html
这道题和上一道题的区别是，数组中可能有相同的数。那么，分下列几种情况：

    def findMin(self, num):
        L = 0; R = len(num)-1
        while L < R and num[L] >= num[R]:
            M = (L+R)/2
            if num[M] > num[L]:
                L = M + 1
            elif num[M] < num[R]:
                R = M
            else:
                L += 1
        return num[L]

https://leetcode.com/discuss/60147/super-simple-and-clean-java-binary-search
public int findMin(int[] nums) { int l = 0, r = nums.length-1; while (l < r) { int mid = (l + r) / 2; if (nums[mid] < nums[r]) { r = mid; } else if (nums[mid] > nums[r]){ l = mid + 1; } else { r--; //nums[mid]=nums[r] no idea, but we can eliminate nums[r]; } } return nums[l]; }
https://leetcode.com/discuss/13775/one-simple-and-clear-method-with-o-1-space-and-worst-o-n-time
int findMin(vector<int> &num) { if(num.empty()) return 0; int i=0,j=num.size()-1; while(i<j) { int mid=(i+j)/2; if(num[j]<num[mid]){ i=mid+1; } else if(num[mid]<num[j]){ j=mid; } else{//num[mid]==num[j] if(num[i]==num[mid]){//linear complexity i++; j--; } else j=mid; } } return num[j]; }

int findMin(vector<int>& nums) { int left=0, right=nums.size()-1; while(nums[left]>=nums[right] && left<right) { int mid=left+((right-left)>>1); if(nums[mid]>nums[right]) left=mid+1; else if(nums[mid]<nums[right] || nums[mid]!=nums[left]) right=mid; else { ++left, --right; } } return nums[left]; }

X.
https://leetcode.com/discuss/66898/only-two-more-lines-code-on-top-of-the-solution-for-part-i
public int findMin(int[] nums) { if (nums == null || nums.length == 0) { return Integer.MIN_VALUE; } int start = 0, end = nums.length - 1; //only need to add the following while loop on top of the solution //for Part I //if two line segments have overlap, remove the overlap. //so, the problem can be solved as Part I while (nums[end] == nums[start] && end > start) { end--; } while (start < end) { //if the linear monotonically increasing in [start, end] if (nums[start] < nums[end]) { return nums[start]; } int mid = start + (end - start) / 2; if (nums[mid] >= nums[start]) { start = mid + 1; } else { end = mid; } } return nums[start]; }
https://tenderleo.gitbooks.io/leetcode-solutions-/content/GoogleMedium/154.html

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

        return nums[l];
    }




X. Recursive
http://www.programcreek.com/2014/03/leetcode-find-minimum-in-rotated-sorted-array-ii-java/

This is a follow-up problem of finding minimum element in rotated sorted array without duplicate elements. We only need to add one more condition, which checks if the left-most element and the right-most element are equal. If they are we can simply drop one of them. In my solution below, I drop the left element whenever the left-most equals to the right-most.

public int findMin(int[] num) { return findMin(num, 0, num.length-1); }   public int findMin(int[] num, int left, int right){ if(right==left){ return num[left]; } if(right == left +1){ return Math.min(num[left], num[right]); } // 3 3 1 3 3 3   int middle = (right-left)/2 + left; // already sorted if(num[right] > num[left]){ return num[left]; //right shift one }else if(num[right] == num[left]){ return findMin(num, left+1, right); //go right }else if(num[middle] >= num[left]){ return findMin(num, middle, right); //go left }else{ return findMin(num, left, middle); } }

X. Different solutions: Find min first
https://discuss.leetcode.com/topic/3538/concise-o-log-n-binary-search-solution

    int search(int A[], int n, int target) {
        int lo=0,hi=n-1;
        // find the index of the smallest value using binary search.
        // Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
        // Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
        while(lo<hi){
            int mid=(lo+hi)/2;
            if(A[mid]>A[hi]) lo=mid+1;
            else hi=mid;
        }
        // lo==hi is the index of the smallest value and also the number of places rotated.
        int rot=lo;
        lo=0;hi=n-1;
        // The usual binary search and accounting for rotation.
        while(lo<=hi){
            int mid=(lo+hi)/2;
            int realmid=(mid+rot)%n;
            if(A[realmid]==target)return realmid;
            if(A[realmid]<target)lo=mid+1;
            else hi=mid-1;
        }
        return -1;
    }

https://leetcode.com/discuss/19638/accepted-solution-and-time-complexity

It is O(n) in the worst case. Run a time complexity analysis of your code for an array with the same element repeated.

In fact it can be proved that worst case complexity cannot be better than O(n). Simply consider the case of an array with all indices set to 1 except for one which is set to 0. Now, this 0 could be anywhere in the array, and you can't possibly know where it is without looking at each possible index.

http://www.jiuzhang.com/solutions/find-minimum-in-rotated-sorted-array-ii/

    public int findMin(int[] num) {
        int min = num[0];
        for (int i = 1; i < num.length; i++) {
            if (num[i] < min)
                min = num[i];
        }
        return min;
    }

在面试中这种问题还是比较常见的，现在的趋势是面试官倾向于从一个问题出发，然后follow up问一些扩展的问题，而且这个题目涉及到了复杂度的改变，所以面试中确实是一个好题，自然也更有可能出现哈。