I try to detect the duplicate in quicksort, but why it's so slow?


  • 0
    B

    I think it's a good idea to detect the duplicates in quicksort, it should work and work fast, but it passed the test cases with a bad speed, could someone tell me why? Is it the algorithm or my code the one to be blamed for?

    bool quickSortWithDupDetect(int* nums, int startP, int endP);
    
    bool containsDuplicate(int* nums, int numsSize) {
        return quickSortWithDupDetect(nums, 0, numsSize-1);
    }
    
    bool quickSortWithDupDetect(int* nums, int startP, int endP)
    {
        if ( startP >= endP )
            return false;
        int i = startP;
        int j = endP;
        //int currP = startP;
        int key = nums[startP];
        while ( i != j ){
            while ( i < j && key < nums[j])
                --j;
            if ( i == j )
                break;
            if ( key == nums[j] )
                return true;
            nums[i] = nums[j];
            while ( i < j && key > nums[i])
                ++i;
            if ( i == j )
                break;
            if ( key == nums[i] )
                return true;            
            nums[j] = nums[i];
            }
        nums[i] = key;
        return quickSortWithDupDetect(nums, startP, i-1) || quickSortWithDupDetect(nums, i+1, endP);    
        
    }

  • 2
    M

    Time complexity of quick sort is O(n*log(n)), or O(n^2) in some worst cases. Maybe you should use hashset and do an one pass scan, and the time complexity is O(n). If you do want to use quick sort, don't select the first element as the pivot key, select a random element instead. That can make the time compliexity be O(n*log(n)) in some worst cases.


Log in to reply
 

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