《剑指 offer》 学习29之最小的 K 个数

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 题目链接：牛客网

解题思路

快速选择

复杂度：O(N) + O(1)只有当允许修改数组元素时才可以使用

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l…j-1] 小于等于 a[j]，且 a[j+1…h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素，这种找第 K 个元素的算法称为快速选择算法。

import java.util.*; public class Main { public static void main(String[] args) { int[] nums = {4,5,1,6,2,7,3,8}; ArrayList list = getLeastNumbers_Solution(nums,4); printList(list); } public static ArrayList<Integer> getLeastNumbers_Solution(int[] nums,int k) { ArrayList<Integer> list = new ArrayList(); if (k > nums.length || k <= 0) { return list; } findKthSmallest(nums,k - 1); // findKthSmallest 会改变数组，使得前 k 个数都是最小的 k 个数 for (int i = 0;i < k;i++) { list.add(nums[i]); } return list; } public static void findKthSmallest(int[] nums,int k) { int l = 0; int h = nums.length - 1; while (l < h) { int j = partition(nums, l, h); if (j == k) { break; } if (j > k) { h = j - 1; }else { l = j + 1; } } } public static int partition(int[] nums,int l,int h) { int p = nums[l]; // 切分元素 int i = l, j = h + 1; while(true) { while (i != h && nums[++i] < p); while (j != l && nums[--j] > p); if (i >= j) { break; } swap(nums, i, j); } swap(nums,l,j); return j; } public static void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } public static void printList(ArrayList list) { for (int i = 0;i < list.size();i++) { System.out.print(list.get(i) + " "); } } }

大小为 K 的最小堆

复杂度：O(NlogK) + O(K)特别适合处理海量数据

应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。

维护一个大小为 K 的最小堆过程如下：在添加一个元素之后，如果大顶堆的大小大于 K，那么需要将大顶堆的堆顶元素去除。

import java.util.*; public class Main { public static void main(String[] args) { int[] nums = {4,5,1,6,2,7,3,8}; ArrayList list = getLeastNumbers_Solution(nums,4); printList(list); } public static ArrayList<Integer> getLeastNumbers_Solution(int[] nums,int k) { ArrayList<Integer> list = new ArrayList(); if (k > nums.length || k <= 0) { return list; } PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); for (int num : nums) { maxHeap.add(num); if (maxHeap.size() > k) { maxHeap.poll(); } } return new ArrayList<>(maxHeap); } public static void printList(ArrayList list) { for (int i = 0;i < list.size();i++) { System.out.print(list.get(i) + " "); } } }

测试结果