输出前k大的数
题目来源OpenJudge
对于这道题目,最简单的方法就是直接运用quick sort对数组进行排序。虽然这样也能得到结果,不过效率非常低(nlogn)。
有没有更高效的方法呢?答案是有的,运用quick sort的分治思想,其实就是快排的变种。
快速排序的思想就是找出一个key,然后用数组其他的数字和它进行对比,大于等于key就放在key的右边。小于等于key放在key的左边。这样便利完一遍,就会出现一侧小于等于key和一侧大于等于key的情况。
当key的右侧一共有k个元素的时候,就达到我们的目的了。
(设数组起始下标为p,结束下边为r,基准元素下标为q,元素的个数为n,数组为nums)
- 应用快速排序的思想,一趟快速排序后,q左边的所有元素都<=nums[q],q右边的所有元素都>=nums[q]。
- 此时若q右边的元素个数即(k == n-q-1)刚好等于K就rerturn
- 如果右边的元素个数少于K,那么在[p, q]的范围内(这里就是q左侧的元素包括q本身)再找前(k-(n-q-1))大的数
n - q - 1代表q右侧的元素(不包括q本身),所以k-(n-q-1)代表还需要的元素。 - 否则就继续在[q+1, r]的范围内找前k大的数
最后算出来的时间复杂度为(n+klogk)
下面是实现代码
import java.util.Arrays;
import java.util.Scanner;
public class Noi7617 {
private static int n;
private static int k;
private static int index;
public static int[] quickSort2(int[] nums) {
return quickSort2(nums, 0, nums.length - 1);
}
public static int[] quickSort2(int[] nums, int p, int r) {
if(p < r) {
int q = partition2(nums, p, r);
// 这里对应上面的第2种情况,-1目的是为了去掉nums[q]的干扰,只要q右侧的元素个数。
if(k == n - q - 1) {
index = q + 1;
return nums;
// 这里对应上面的第3种情况
} else if(k > n - q - 1) {
// 修改还需要的k
k = k - (n - q - 1);
// 取q的左侧(包括q)元素个数给n
n = q + 1;
quickSort2(nums, p, q);
// 这里对应上面的第4种情况
} else if(k < n - q - 1) {
quickSort2(nums, q + 1, r);
}
}
return nums;
}
public static int partition2(int[] nums, int p, int r) {
int i = p;
int j = r + 1;
while(true) {
while(nums[++i] < nums[p]);
while(nums[--j] > nums[p]);
if(i >= j) {
break;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
int temp = nums[j];
nums[j] = nums[p];
nums[p] = temp;
return j;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
k = scanner.nextInt();
nums = quickSort2(nums);
Arrays.sort(nums, index , nums.length);
for(int i = nums.length - 1; i >= index; i--) {
System.out.println(nums[i]);
}
}
}