알고리즘,자료구조
Finding Kth largest element in Array
[하마] 이승현 (wowlsh93@gmail.com)
2015. 5. 12. 16:41
public class KthLargest {
public static void main(String[] args) {
int[] x = new int[] { 3, 6, 92, 34, 1, 35, 62, 13, 12, 24, 53 };
System.out.println(getKthLargest(x, 3));
}
private static int getKthLargest(int[] x, int k) {
int low = 0;
int high = x.length - 1;
while (true) {
int pivot = (low + high) / 2;
int newPiv = partition(x, low, high, pivot);
if (newPiv == k) {
return x[newPiv];
} else if (newPiv < k) {
low = newPiv + 1;
} else {
high = newPiv - 1;
}
}
}
private static int partition(int[] x, int left, int right, int pivot) {
int pivValue = x[pivot];
swap(x, pivot, right);
int storePos = left;
for (int i = left; i < right; i++) {
if (x[i] < pivValue) {
swap(x, i, storePos);
storePos++;
}
}
swap(x, storePos, right);
return storePos;
}
private static void swap(int[] x, int a, int b) {
int temp = x[a];
x[a] = x[b];
x[b] = temp;
}
}