Skip to content

Instantly share code, notes, and snippets.

@deyindra
Last active May 30, 2016 04:28
Show Gist options
  • Save deyindra/ea65320cd4b87bb37c9cf050b581b6ef to your computer and use it in GitHub Desktop.
Save deyindra/ea65320cd4b87bb37c9cf050b581b6ef to your computer and use it in GitHub Desktop.
Find Kth largest or Kth smallest element using Median of Median algorithm
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
public class KthElement {
private static <T extends Comparable<T>> T getMedian(List<T> list){
Collections.sort(list);
return list.get(list.size() / 2);
}
private static <T extends Comparable<T>> T findMediansOfMedians(List<T> list){
int size = list.size();
if(size<=5){
return getMedian(list);
}else{
List<T> medians = new ArrayList<>();
for (int i = 0; i < list.size() - list.size() % 5; i = i + 5){
medians.add(getMedian(list.subList(i, i + 5)));
}
return findMediansOfMedians(medians);
}
}
public static <T extends Comparable<T>> T findKthElement(List<T> list, final int k, boolean isMin){
T median = findMediansOfMedians(list);
List<T> left = new ArrayList<>();
List<T> right = new ArrayList<>();
if(isMin){
left.addAll((list.stream().parallel().filter(obj -> median.compareTo(obj) > 0).collect(Collectors.toList())));
right.addAll(list.stream().parallel().filter(obj -> median.compareTo(obj) < 0).collect(Collectors.toList()));
}else{
left.addAll((list.stream().parallel().filter(obj -> median.compareTo(obj) < 0).collect(Collectors.toList())));
right.addAll(list.stream().parallel().filter(obj -> median.compareTo(obj) > 0).collect(Collectors.toList()));
}
if(k<=left.size()){
return findKthElement(left,k, isMin);
}else if(k==left.size()+1){
return median;
}else{
return findKthElement(right,k-left.size()-1, isMin);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment