Created
February 17, 2019 00:41
-
-
Save leeelton/b1c0e339dbfb84e3db2730afcbccd369 to your computer and use it in GitHub Desktop.
quick select, find nth largest number
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-(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