Are we always getting a 3-way partition after we do a quickSelect(selecting kth smallest element)??


  • 0

    I am doing WiggleSortII,and I see that people're using quickSelect to select median, so I did this.

    To raise an example, we have {5,3,1,2,6,7,8,5,5}, and for median,I want to get 5th smallest element.

    I was thinking that quickSelect could bring me something like {S,S,S,M,M,M,L,L}
    S-number smaller than median
    M-number equals to median
    L-number greater than median, so I could cut the array into two parts,from middle,reverse two parts and rearrange it in a wiggle way, i.e to merge M S S S and L L M M

    But my quickSelect code bring me {2,3,1,5,5,7,8,5,6}, median is 5 which is correct, but 5 are distributed on both sides of median index and all 5 aren't put together.

    Can quickSelect bring us 3 partition?


Log in to reply
 

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