剑指offer—40.最小的K个数—分析及代码(Java)

一、题目

输入 n 个整数，找出其中最小的 K 个数。例如输入4, 5, 1, 6, 2, 7, 3, 8 这 8 个数字，则最小的 4 个数字是 1, 2, 3, 4。

二、分析及代码

1. 排序

（1）思路

最直观的方法：对数组进行排序，前 k 个数即为所求解。
这种方法简单直观，但时间复杂度较高，为 O(nlogn)。

（2）代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (input == null || input.length < k)
            return ans;
        Arrays.sort(input);
        for (int i = 0; i < k; i++)
            ans.add(input[i]);
        return ans;
    }
}

（3）结果

运行时间：17 ms，占用内存：9480 K。

2. Partition

（1）思路

可结合快速排序中的 Partition 方法，通过迭代将最小的 K 个数全部交换到前 K 个位置。
这种方法时间复杂度为 O(n)。

（2）代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ans = new ArrayList<>();
         if (input == null || input.length == 0 || k <= 0 || k > input.length)
            return ans;
        int begin = 0, end = input.length - 1;
        int p = Partition(input, begin, end);
        while (p != k - 1) {
            if (p < k - 1)
                begin = p + 1;
            else
                end = p - 1;
            p = Partition(input, begin, end);
        }
        for (int i = 0; i < k; i++)
            ans.add(input[i]);
        return ans;
    }
     
    public int Partition(int[] input, int begin, int end) {
        int pivot = input[begin];
        int low = begin, high = end;
        while (low < high) {
            while (low != high && input[high] >= pivot)
                high--;
            swap(input, low, high);
            while (low != high && input[low] <= pivot)
                low++;
            swap(input, low, high);
        }
        return high;
    }
     
    public void swap(int[] input, int a, int b) {
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }
}

（3）结果

运行时间：23ms，占用内存：9628。

3. 堆

（1）思路

可以建立一个容量为 k 的大顶堆，当堆中元素个数 < k 时，添加遍历到的元素；当堆中元素个数等于 k 时，若遍历到的元素小于堆顶，抛出堆顶元素并加入新元素，否则跳过遍历到的元素。
这种方法时间复杂度为 O(nlogk)，特别适合处理数据流。

（2）代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ans = new ArrayList<>();
         if (input == null || input.length == 0 || k <= 0 || k > input.length)
            return ans;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer> (k, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return b.compareTo(a);
            }
        });
        
        for (int i = 0; i < input.length; i++) {
            if (maxHeap.size() < k)
                maxHeap.offer(input[i]);
            else if (input[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(input[i]);
            }
        }
        
        for (Integer i : maxHeap) {
            ans.add(i);
        }
        return ans;
    }
}

（3）结果

运行时间：23ms，占用内存：9536。

三、其他

暂无。