本文主要是介绍Find Kth题目类型总结 (quick Select 类型总结)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先quick select算法的模板要倒背如流，这个是通过quick sort里面提炼得到的算法；两个while一个if，condition相同；后面再递归
Kth Largest Element in an Array (是找从大到小的第k大；注意左边是大的，右边是小的，quick select的模板要熟记)
class Solution {public int findKthLargest(int[] nums, int k) {if(nums == null || nums.length == 0) {return -1;}return findKth(nums, 0, nums.length - 1, k);}private int findKth(int[] nums, int start, int end, int k) {if(start == end) {return nums[start];}int i = start; int j = end;int mid = start + (end - start) / 2;int pivot = nums[mid];while(i <= j) {while(i <= j && nums[i] > pivot) {i++;}while(i <= j && nums[j] < pivot) {j--;}if(i <= j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;i++;j--;}}if(start + k - 1 <= j){return findKth(nums, start, j, k);}if(start + k - 1 >= i) {return findKth(nums, i, end, k - (i - start));}return nums[j + 1];}
}Kth Smallest Numbers in Unsorted Array (quickselect标准解法：O(N);)
Sort Colors II (rainbow sort) 思路：按照quick sort的思想来，start, end是数组起点，终点的范围，from to 是颜色的范围，用颜色的中间值，作为pivot，然后小的在左边，大的在右边，先整体有序，再局部有序；注意 start >= end || from >= to base条件的判断，还有midcolor属于左边；
public class Solution {/*** @param colors: A list of integer* @param k: An integer* @return: nothing*/public void sortColors2(int[] colors, int k) {if(colors == null || colors.length == 0) {return;}int n = colors.length;quickSelect(colors, 0, n - 1, 1, k);}private void quickSelect(int[] colors, int start, int end, int from, int to) {if(start >= end || from >= to) { // 注意这个base条件的判断，否则出错；return;}int midcolor = from + (to - from) / 2;int i = start; int j = end;while(i <= j) {// midcolor 属于左边；while(i <= j && colors[i] <= midcolor) {i++;}while(i <= j && colors[j] > midcolor) {j--;}if(i <= j) {int temp = colors[i];colors[i] = colors[j];colors[j] = temp;i++;j--;}}// j , i;quickSelect(colors, start, j, from, midcolor); // midcolor属于左边；quickSelect(colors, i, end, midcolor + 1, to);}
}Kth Largest Element II 思路：可以用quick select模板,注意模板是两个while一个if，另外条件是i <= j ,但是如果数据量特别大，内存存不下的时候，就要用pq，minheap；
public class Solution {/*** @param nums: an integer unsorted array* @param k: an integer from 1 to n* @return: the kth largest element*/public int kthLargestElement2(int[] nums, int k) {if(nums == null || nums.length == 0) {return -1;}PriorityQueue<Integer> minheap = new PriorityQueue<Integer>();for(int num : nums) {if(minheap.size() < k) {minheap.offer(num);} else {// minheap.size() > k;if(num > minheap.peek()) {minheap.poll();minheap.offer(num);}}}return minheap.peek();}
}Nuts bolts problem 思路：算法比较好想，就是用A最左边的一个pivot， 去sort B，然后用B[index] = A[l] ,去sort A，然后recursion；每次用start，去sort另外一个数组，首先把match的放到B的头部，然后partition后面的部分，partition完了之后，把start换到j的位子，这样才是一个正确的顺序；
/*** public class NBCompare {* public int cmp(String a, String b);* }* You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",* if "a" is bigger than "b", it will return 1, else if they are equal,* it will return 0, else if "a" is smaller than "b", it will return -1.* When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
public class Solution {/*** @param nuts: an array of integers* @param bolts: an array of integers* @param compare: a instance of Comparator* @return: nothing*/public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {int n = nuts.length;sort(nuts, bolts, compare, 0, n - 1);}private void sort(String[] nuts, String[] bolts, NBComparator compare, int start, int end){if(start >= end) {return;}String pivot = bolts[start];int index = partition(nuts, compare, start, end, pivot);partition(bolts, compare, start, end, nuts[index]);sort(nuts, bolts, compare, start, index - 1);sort(nuts, bolts, compare, index + 1, end);}private int partition(String[] strs, NBComparator compare, int start, int end, String pivot) {for(int i = start; i <= end; i++) {if(compare.cmp(strs[i], pivot) == 0 || compare.cmp(pivot, strs[i]) == 0) {swap(strs, start, i);break;}}int i = start + 1; int j = end;while(i <= j) {while(i <= j && (compare.cmp(strs[i], pivot) == -1 || compare.cmp(pivot, strs[i]) == 1)) {i++;}while(i <= j && (compare.cmp(strs[j], pivot) == 1 || compare.cmp(pivot, strs[j]) == -1)) {j--;}if(i <= j) {swap(strs, i, j);i++;j--;}}swap(strs, start, j); // 一定要把头部换到j，这样才是一个正确的顺序；return j;}private void swap(String[] A, int i, int j) {String temp = A[i];A[i] = A[j];A[j] = temp;}
};Kth Smallest Element in a Sorted Matrix (两种做法：klogk, (x, y) 被下面和右边的元素压着，那么用pq从小到大排序，然后依次把下面和右边的元素加入pq。另外一种，Binary Search，count value <= mid的元素有多少个，如果<k个，那么第K大的元素在后面,start = mid; 如果 count >= k个，那么 end = mid; 就是用start和end去逼近那个刚好<=k的值。nlogn; )
Kth Smallest Sum In Two Sorted Arrays (这题把两个sort array每一行跟每一列元素加一下
1+2, 1+4, 1+6
7+2, 7+4, 7+6
11+2, 11+4, 11+6, 那么这题从左到右也是递增的，从上到下也是递增的，这题就完完全全变成了上面的一题；代码都不需要变化多少，matrix[i][j] = A[i] + A[j]; O(klogk)
Merge k Sorted Lists (这题可以用PQ解决，每次加入队伍的开头，然后取走之后，加入第二大的）另外一种方法就是 利用 merge sort的原理，如果我会做 Merge Two Sorted Lists 那么可以用merge sort原理，劈成两半，然后分别sort。O(nlogk)
Kth Smallest Element in a BST (这里就是inorder traverse的stack版本，然后用count一下即可）关于Tree的traverse和divide conquer可以参考: PreOrder, InOrder, PostOrder 题型总结
Median of two Sorted Arrays 基于 FindKth 的算法。整体思想类似于 median of unsorted array 可以用 find kth from unsorted array 的解题思路。
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;int k = (n + m) / 2;if((n + m) % 2 == 0) {return 0.5 * (findKth(nums1, 0, nums2, 0, k) + findKth(nums1, 0, nums2, 0, k + 1));} else {return (double)findKth(nums1, 0, nums2, 0, k + 1);}}private int findKth(int[] A, int astart, int[] B, int bstart, int k) {if(astart >= A.length) {return B[bstart + k - 1];}if(bstart >= B.length) {return A[astart + k - 1];}if(k == 1) {return Math.min(A[astart], B[bstart]);}int midA = astart + k/2 - 1 >= A.length ? Integer.MAX_VALUE : A[astart + k/2 - 1];int midB = bstart + k/2 - 1 >= B.length ? Integer.MAX_VALUE : B[bstart + k/2 - 1];if(midA < midB) {return findKth(A, astart + k/2, B, bstart, k - k/2);} else{return findKth(A, astart, B, bstart + k/2, k - k/2);}}
}Kth Largest in N Arrays 思路：可以swap elements in array，也就是array内部可以sort，sort完之后，从最后每次取最大的，然后用maxheap去找最大的，取走一个，找接下来第二大的入pq；
public class Solution {/*** @param arrays: a list of array* @param k: An integer* @return: an integer, K-th largest element in N arrays*/private class Node {public int x;public int y;public int val;public Node(int x, int y, int val) {this.x = x;this.y = y;this.val = val;}}public int KthInArrays(int[][] arrays, int k) {if(arrays == null || arrays.length == 0 ) {return -1;}PriorityQueue<Node> pq = new PriorityQueue<Node>(k, (a, b) -> (b.val - a.val));int n = arrays.length;for(int i = 0; i < n; i++) {Arrays.sort(arrays[i]);if(arrays[i].length > 0) {int lastIndex = arrays[i].length - 1;pq.offer(new Node(i, lastIndex, arrays[i][lastIndex]));}}int count = 0;while(!pq.isEmpty()) {Node node = pq.poll();count++;if(count == k) {return node.val;}if(node.y - 1 >= 0) {pq.offer(new Node(node.x, node.y - 1, arrays[node.x][node.y - 1]));}}return -1;}
}Find K Closest Elements 思路：先找到起始start point，然后用打擂台的方法O(K)的去取得最近的值；
class Solution {public List<Integer> findClosestElements(int[] arr, int k, int x) {List<Integer> list = new ArrayList<Integer>();if(arr == null || arr.length == 0) {return list;}int index = findCloset(arr, x);list.add(arr[index]);int i = index-1; int j = index+1;int count = 1;while(count < k) {if(0 <= i && j < arr.length) {if(x - arr[i] <= arr[j] - x) {list.add(0,arr[i--]);} else {list.add(arr[j++]);}} else if(i < 0 && j < arr.length) {list.add(arr[j++]);} else if(i >= 0 && j >= arr.length) {list.add(0,arr[i--]);}count++;}return list;}private int findCloset(int[] A, int target) {int start = 0; int end = A.length - 1;while(start + 1 < end) {int mid = start + (end - start) / 2;if(A[mid] == target) {return mid;} else if(A[mid] < target) {start = mid;} else {end = mid;}}// 如果等于的话，那么取前面的start；if(target - A[start] <= A[end] - target) {return start;}return end;}
}Find Median from Data Stream (nlogk, 用两个堆来维持关系，左边用最大堆，右边用最小堆，如果num[i] 比最大堆的堆顶小，加入最大堆，否则加入最小堆，然后再调整数目，始终保证最大堆比最小堆数目相等，或者只大于1；)
public class Solution {/*** @param nums: A list of integers* @return: the median of numbers*/private PriorityQueue<Integer> maxheap, minheap;public int[] medianII(int[] A) {if(A == null || A.length == 0) {return new int[0];}int n = A.length;maxheap = new PriorityQueue<Integer>(n, Collections.reverseOrder());minheap = new PriorityQueue<Integer>(n);int[] res = new int[n];for(int i = 0; i < A.length; i++) {if(maxheap.isEmpty() || A[i] <= maxheap.peek()){maxheap.offer(A[i]);} else {minheap.offer(A[i]);}balance();res[i] = maxheap.peek();}return res;}private void balance() {// 保证maxheap的size总是比minheap相等或者大于1；while(maxheap.size() < minheap.size()){maxheap.offer(minheap.poll());}while(minheap.size() < maxheap.size() - 1){minheap.offer(maxheap.poll());}}
}Sliding Window Median (跟 Find Median from Data Stream类似，用maxheap minheap去维持中位数，不同的地方就是window移动的时候，需要把头部的元素给去掉，注意后面一定要再balance一下；)
public class Solution {/*** @param nums: A list of integers* @param k: An integer* @return: The median of the element inside the window at each moving*/private PriorityQueue<Integer> maxheap, minheap;public List<Integer> medianSlidingWindow(int[] nums, int k) {List<Integer> list = new ArrayList<Integer>();if(nums == null || nums.length == 0 || k <= 0) {return list;}maxheap = new PriorityQueue<Integer>(k / 2 +1, Collections.reverseOrder());minheap = new PriorityQueue<Integer>(k);int n = nums.length;for(int i = 0; i < n; i++) {if(maxheap.size() == 0 || nums[i] <= maxheap.peek()){maxheap.offer(nums[i]);} else {minheap.offer(nums[i]);}balance();if(i == k - 1) { // 这个刚刚等于k的时候，只需要加入list；list.add(maxheap.peek());}if(i >= k) { // i >= k的时候就要开始踢人了；int dropNum = nums[i - k];remove(dropNum);balance(); // drop之后一定要balance一下，因为会出现不均衡情况；list.add(maxheap.peek());}}return list;}// remove的时候只需要跟值进行比较就可以，所以minheap maxheap里面存的都是值；不是index；private void remove(int dropNum) {if(dropNum <= maxheap.peek()){maxheap.remove(dropNum);} else {minheap.remove(dropNum);}}private void balance() {while(maxheap.size() < minheap.size()) {maxheap.offer(minheap.poll());}while(minheap.size() < maxheap.size() - 1){minheap.offer(maxheap.poll());}}
}Top K Frequent Words 思路：注意这个题目需要最大到最小输出，用maxheap，Nlogk;
class Solution {private class Node {public String word;public int fre;public Node(String word, int fre) {this.word = word;this.fre = fre;}}public List<String> topKFrequent(String[] words, int k) {List<String> list = new ArrayList<String>();HashMap<String, Integer> countmap = new HashMap<String, Integer>();for(String word: words) {countmap.put(word, countmap.getOrDefault(word, 0) + 1);}PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> (a.fre != b.fre ?b.fre - a.fre : a.word.compareTo(b.word)));for(String word: countmap.keySet()) {pq.offer(new Node(word, countmap.get(word)));}while(!pq.isEmpty() && k > 0) {list.add(pq.poll().word);k--;}return list;}
}这篇关于Find Kth题目类型总结 (quick Select 类型总结)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
