Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- Quick Selection Time = O(n)
- Quick Selection T(n) = T(n/2) + O(n) = T(n/4) + O(n/2) + O(n) = O(n + n/2 + n/4 + ...+ 1) = O(2n)
- Quick Sort T(n) = 2T(n/2) + O(n) = 4T(n/4) + 2*O(n/2) + O(n) = logn * O(n) = nlogn
- */
- public static void main(String[] args) {
- Solution sol = new Solution();
- int[] nums = new int[]{-4,6,1,76,2,3,3,5};
- System.out.print(sol.quickSelection(nums, 8));
- }
- public int quickSelection(int[] nums, int k) {
- return partition(nums, 0, nums.length - 1, k);
- }
- private int partition(int[] nums, int left, int right, int k) {
- if (left == right) return nums[left];
- int pivotIndex = getPivot(left, right);
- int pos = quickSelect(nums, pivotIndex, left, right);
- if (pos == k - 1) {
- return nums[pos];
- } else if (pos < k - 1) {
- return partition(nums, pos + 1, right, k);
- } else {
- return partition(nums, left, pos - 1, k);
- }
- }
- private int quickSelect(int[] nums, int pivotIndex, int left, int right) {
- int pivot = nums[pivotIndex];
- swap(nums, pivotIndex, right);
- int i = left; int j = right;
- while (i <= j) {
- if (nums[i] > pivot) {
- i++;
- } else if (nums[j] <= pivot) {
- j--;
- } else {
- swap(nums, i++, j--);
- }
- }
- swap(nums, i, right);
- return i;
- }
- private void swap(int[] nums, int i, int j) {
- int temp = nums[i];
- nums[i] = nums[j];
- nums[j] = temp;
- }
- private int getPivot(int left, int right) {
- Random rd = new Random();
- return left + rd.nextInt(right - left + 1);
- }
Add Comment
Please, Sign In to add comment