I used the randomized Quicksort,but it always be "Time limited exceed"


  • 0
    W

    the worst case of QuickSort is O(n2)
    So I use the randomized QuickSort to avoid the worst case, but I still be "Time limited exceed"?


  • 0
    P

    I guess you randomly locate a pivot node is not O(1) .


  • 0
    L

    I fail to pass a test case where there're lots of duplicate. I guess you might run into the same problem here.

    Say if the list is "1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1", and each time all the 1s will still be on one of the left or right list, depended on how you are dealing with the case of duplicates.

    I think if you randomize the placement of duplicates, you could pass the test case.


  • 0
    L

    Any hints to randomly locate a pivot node in O(1). I only get some hints of O(n).


  • 0
    L

    My Randomized QuickSork which randomly locates a pivot node in O(n) was just accepted. I notice we need not only randomly pick the pivot but also handle the case where all nodes' values are same efficiently.


Log in to reply
 

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