Skip to content

Instantly share code, notes, and snippets.

@leeelton
Created February 17, 2019 00:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save leeelton/b1c0e339dbfb84e3db2730afcbccd369 to your computer and use it in GitHub Desktop.
Save leeelton/b1c0e339dbfb84e3db2730afcbccd369 to your computer and use it in GitHub Desktop.
quick select, find nth largest number
-(void) swapFirst:(int)first withSecond:(int)second inArray:(NSMutableArray *)array
{
NSNumber *temp = array[first];
array[first] = array[second];
array[second] = temp;
return;
}
-(int) findKthLargestNumber:(int)k
inArray:(NSMutableArray *)array
begin:(int)begin
end:(int)end
{
int pivot = (begin + end) / 2;
[self swapFirst:pivot withSecond:end inArray:array];
int pivotPosition = begin;
for (int i = begin; i < end; ++i) {
if ([array[i] intValue] < [array[end] intValue]) {
[self swapFirst:i withSecond:pivotPosition inArray:array];
pivotPosition++;
}
}
[self swapFirst:pivotPosition withSecond:end inArray:array];
if (pivotPosition == k - 1) {
return [array[pivotPosition] intValue];
} else if (pivotPosition < k - 1) {
return [self findKthLargestNumber:k inArray:array begin:pivotPosition + 1 end:end];
} else {
return [self findKthLargestNumber:k inArray:array begin:begin end:pivotPosition - 1];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment