Last active
May 30, 2016 04:28
-
-
Save deyindra/ea65320cd4b87bb37c9cf050b581b6ef to your computer and use it in GitHub Desktop.
Find Kth largest or Kth smallest element using Median of Median algorithm
This file contains hidden or 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
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