10ms C++ solution (but, O(n) with duplicates)


  • 0
    J
        bool search(int A[], int n, int target) {
        int left = 0, right = n - 1;
        
        while(left <= right) {
            while(A[left] == A[left+1] && left < n)
                left++;
            while(A[right] == A[right-1] && right >= 0)
                right--;
            
            int mid = (left + right)/2;
            if(A[mid] == target)
                return true;
            else {
                if(A[left] <= A[mid]) {
                    if(target < A[mid] && target >= A[left])
                        right = mid - 1;
                    else
                        left = mid + 1;
                }
                else {
                    if(target > A[mid] && target <= A[right])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
            }
        }
        
        return false;
    }

  • 0
    E

    This code also consumes 10 ms...

    bool search(vector<int>& nums, int target) {
        if(nums.empty()) return false;
        for(auto a : nums)
            if(a == target) return true;
        return false;
    }

  • 0
    Y

    Why you can use "for" like this?
    for(auto a : nums)
    The commonly use of "for" should be for(int i=0;i<10;i++); what is the different?
    Is your usage of "for" a special function for the vector container?


  • 0
    D

    C++11 standards


Log in to reply
 

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