I squeeze the array to one with no duplicates and then follows the method of the above,but the answer is wrong


  • 0
    L
        class Solution {
    public:
        bool search(int A[], int n, int target) {
            int i=0,index=0;
            for(i=1;i<n;i++)
                if(A[i]!=A[index]) A[++index]=A[i];
                
             int low=0,high=index;
            int mid;
            while(low<=high){
                mid=(low+high)>>1;
               //if (A[mid]==target) return mid;
                if(A[low]>A[mid]){
                    if (A[mid]==target) return true;
                    if(target>A[mid]&&target<=A[high]) low=mid+1;
                    else high=mid-1;
                }
                else {
                    if (A[mid]==target) return mid;
                    if(target<A[mid]&&target>=A[low]) high=mid-1;
                    else low=mid+1;
                }
                
            }
            return false;
        }
    };

  • 2
    S

    If it has already ran a O(N) for-loop to squeeze. Why not just check if target in it by comparing each element?

    As far as I known, having duplicated items can not be solved by less than O(N).


  • 0
    L

    i corrected some mistakes and it accepted,,,so you mean the real goal of the question is to decide the location(index),rather than the existence??,,,,


  • 0
    M

    No, you do want the existence, but to remove the duplicates, you need to know what the value of each element is. Shangrila's point was that since you are checking for duplicates, why not just check for the given node?

    Assume the node you are looking for is a duplicate. Then with your algorithm, you'll find the node and remove all duplicates of it before searching the array of singletons for the node you already found. Just stop when you find it and would check for the duplicates. If you don't find it in your search for duplicates, then it isn't in the array and you can skip the binary search.


Log in to reply
 

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