Find the k-th largest element KThLargestElement.java
public static int findKthLargest(List<Integer> A, int k) {
int left = 0, right = A.size() - 1;
Random r = new Random();
while (left <= right) {
// Generates a random int in [left, right].
int p = partition(left, right, r.nextInt(right - left + 1) + left, A);
if (p == k - 1) {
return A.get(p);
} else if (p > k - 1) {
right = p - 1;
} else { // p < k - 1.
left = p + 1;
}
}
// @exclude
throw new RuntimeException("no k-th node in array A");
// @include
}
// Partitions A according pivot, returns its index after partition.
private static int partition(int left, int right, int pivot,
List<Integer> A) {
int pivotValue = A.get(pivot);
int largerIndex = left;
Collections.swap(A, pivot, right);
for (int i = left; i < right; ++i) {
if (A.get(i) > pivotValue) {
Collections.swap(A, i, largerIndex++);
}
}
Collections.swap(A, right, largerIndex);
return largerIndex;
}
Find the k-th largest element---large n, small $k$
KthLargestElementLargeN.javaprivate static class Greater<T extends Comparable<T>> implements
Comparator<T> {
@Override
public int compare(T o1, T o2) {
return o2.compareTo(o1);
}
public static int findKthLargestUnknownLength(InputStream sin, int k) {
List<Integer> M = new ArrayList<>();
Scanner s = new Scanner(sin);
while (s.hasNextInt()) {
int x = s.nextInt();
M.add(x);
if (M.size() == (k * 2) - 1) {
// Keeps the k largest elements and discard the small ones.
nthElement(M, k - 1, new Greater<Integer>());
M = new ArrayList<>(M.subList(0, k));
}
}
nthElement(M, k - 1, new Greater<Integer>());
return M.get(k - 1); // return the k-th largest one.
}
