题解 | #输入n个整数，输出其中最小的k个#
输入n个整数，输出其中最小的k个
https://www.nowcoder.com/practice/69ef2267aafd4d52b250a272fd27052c
题解思路：输出最小的k个数，我首先想到的是先排序再遍历输出。但排序用哪种方式好呢？感觉冒泡、插入、选择都可以，只需要排出前k个即可，快排和归并感觉不是很有必要，因为这样会将所有数据进行排序，有些多此一举。当然对于Top k 类型的算法，堆排序肯定是最佳的选择。Java中PriorityQueue是通过完全二叉树实现的小顶堆，使用起来很方便，省去了自己构建堆的麻烦。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Scanner scanner = new Scanner(br);
int num = scanner.nextInt();
int k = scanner.nextInt();
int[] nums = new int[num];
for (int i = 0; i < num; i++) {
nums[i] = scanner.nextInt();
}
String result = getSmallestNumberOfK_2(nums,k);
System.out.println(result);
}
// 投机取巧的解法
private static String getSmallestNumberOfK_3(int[] nums, int k) {
if (k <= 0 || nums == null || nums.length == 0) return null;
StringBuilder builder = new StringBuilder();
Arrays.sort(nums);
for (int i = 0; i < k; i++) {
builder.append(nums[i]).append(" ");
}
return builder.toString().trim();
}
// 使用堆排序解决
private static String getSmallestNumberOfK_2(int[] nums, int k) {
if (k <= 0 || nums == null || nums.length == 0) return null;
StringBuilder builder = new StringBuilder();
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int i = 0; i < nums.length; i++) {
heap.add(nums[i]);
}
for (int i = 0; i < k; i++) {
builder.append(heap.poll()).append(" ");
}
return builder.toString().trim();
}
// 使用选择排序解决
private static String getSmallestNumberOfK_1(int[] nums,int k) {
if (k <= 0 || nums == null || nums.length == 0) return null;
StringBuilder builder = new StringBuilder();
selectort(nums,k);
for (int i = 0; i < k; i++) {
builder.append(nums[i]).append(" ");
}
return builder.toString().trim();
}
private static void selectort(int[] nums,int k) {
int min;
for (int i = 0; i < nums.length-1; i++) {
min = i;
for (int j = i+1; j < nums.length; j++) {
if (nums[j] < nums[min]){
min = j;
}
if (i == k) break;
}
if (min != i)
swap(nums,i,min);
}
}
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
投递腾讯等公司10个岗位 >