My accepted java code


  • 6
    S

    The runtime is O(n). I don't think it can be faster

    public int findMin(int[] num) {
            if(num == null || num.length == 0) {
                return -1; // should throw an exception, not sure if leetcode supports it
            }
            int l = 0;
            int r = num.length-1;
            while(l < r) {
                if(num[l] < num[r]) {
                    return num[l];
                }
                int m = l + (r-l)/2;
                if(num[l] > num[m]) {
                    r = m;
                } else if(num[l] < num[m]) {
                    l = m+1;
                } else { // num[l] == num[m]
                    if(num[l] == num[r]) {
                        l++;
                        r--;
                    } else { // only the num[l] == num[m] >  num[r] case left
                        l = m+1;
                    }
                }
            }
            return num[l];
        }

  • 0
    S

    Sorry that I forgot to format my code. Now it displays correctly.


  • 0
    S

    This is my C++ code: AC in 24ms

    class Solution {
    
    public:
    
        int findMin(vector<int> &num) {
    
        int n = num.size();
    
        if (n == 0) return 0;
        int left = 0, right = n-1, mid;
        while (right > 0 && num[right] == num[right-1]) right--;
        while (left < right && num[left] == num[right]) left++;
        if (num[left] <= num[right]) return num[left];
    
        while (right > left + 1){
            while (right > left + 1 && right > 0 && num[right] == num[right-1]) right--;
            int mid = (right - left) / 2 + left;
    
            if (num[left] > num[mid])
                right = mid;
            else
                left = mid;
        }
            return num[right];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.