题目描述
有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。
思路:快排 + 二分
用快速排序思想把数组按降序排列,第K大元素的下标就是 targetPos = K-1
(如果按升序排列数组,第K大元素的下标就是n - K,代码要稍微改动一下,但思想都一样,看哪个更顺手了)
每次partition后数组被分为三段:a[0...pivot-1], a[pivot], a[pivot + 1, end]
比较pivot 和 targetPos的大小,若相等则返回a[pivot];
若不相等(大小关系看代码),这时就可以排除数组的一半了,则递归调用quickSort排序数组的剩余目标位置
时间复杂度:每次排除一半的元素,partition比较加交换需要操作n次,则 n + n/2 + n/4 + ... + 1,这是公比为1/2的等比数列,
Sn = a1(1 - q^n)/ (1 - q), 带入数字得2n
所以 时间复杂度为 O(n)
降序排列数组
import java.util.*; //时间复杂度O(n) // public class Finder { public int findKth(int[] a, int n, int K) { // write code here int targetPos = K - 1; return quickSort(a, 0, n-1, targetPos); } private int quickSort(int[] a, int start, int end, int pos) { int pivot = partition(a, start, end); if (pivot == pos) return a[pos]; else if (pivot < pos) return quickSort(a, pivot + 1, end, pos); else return quickSort(a, start, pivot - 1, pos); } private int partition(int[] a, int start, int end) { int pivot = end; int count = start; for (int i = start; i < end; i++) { if (a[i] > a[pivot]) { swap(a, i, count++); //count++; } } swap(a, count, pivot); return count; } private void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } }
升序排列数组
import java.util.*; public class Finder { public int findKth(int[] a, int n, int K) { // write code here int targetPos = n - K; return quickSort(a, 0 , n-1, targetPos); } private int quickSort(int[] a, int start, int end, int pos) { int pivot = partition(a, start, end); if (pivot == pos) return a[pos]; else if (pivot < pos) return quickSort(a, pivot + 1, end, pos); else return quickSort(a, start, pivot - 1, pos); } private int partition(int[] a, int start, int end) { int pivot = end; int count = start; for (int i = start; i < end; i++) { if (a[i] < a[pivot]) { swap(a, i, count); count++; } } swap(a, count, pivot); return count; } private void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } }