Java刷题：最小k个数

在Java中，寻找最小的k个数是一个常见的面试问题，通常用于考察算法的效率和数据结构的应用。这个问题可以通过多种方法解决，比如使用排序、堆（优先队列）或快速选择算法。接下来，我们将介绍这几种方法，并给出示例代码。

方法一：排序法

最直接的方法是将数组进行排序，然后返回前k个元素。这个方法的时间复杂度为O(n log n)，因为排序是主要的时间开销。

import java.util.Arrays;

public class KSmallestNumbers {
    public static int[] getLeastNumbers(int[] arr, int k) {
        if (k <= 0 || k > arr.length) {
            return new int[0]; // 返回空数组
        }
        Arrays.sort(arr); // 对数组进行排序
        return Arrays.copyOfRange(arr, 0, k); // 返回前k个元素
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int[] result = getLeastNumbers(arr, k);
        System.out.println(Arrays.toString(result)); // 输出：[1, 2]
    }
}

方法二：堆（优先队列）

使用最小堆（或最大堆）可以提高效率，时间复杂度为O(n log k)。我们可以维护一个大小为k的最大堆，这样在遍历数组时，只有比堆顶元素小的元素才会被加入堆中。

import java.util.Collections;
import java.util.PriorityQueue;

public class KSmallestNumbersUsingHeap {
    public static int[] getLeastNumbers(int[] arr, int k) {
        if (k <= 0 || k > arr.length) {
            return new int[0];
        }

        // 创建一个最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int num : arr) {
            maxHeap.add(num);
            if (maxHeap.size() > k) {
                maxHeap.poll(); // 移除堆顶元素
            }
        }

        // 将堆中的值放入结果数组
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int[] result = getLeastNumbers(arr, k);
        System.out.println(Arrays.toString(result)); // 输出：[2, 1]
    }
}

方法三：快速选择算法

快速选择（QuickSelect）是一种优化的选择算法，时间复杂度为O(n)期望。它与快速排序类似，通过选定一个pivot元素，将数组分成左边（小于pivot）和右边（大于pivot）的两部分。根据pivot的位置，我们可以判断k个元素位于左半部分还是右半部分。

import java.util.Random;

public class KSmallestNumbersUsingQuickSelect {
    public static int[] getLeastNumbers(int[] arr, int k) {
        if (k <= 0 || k > arr.length) {
            return new int[0];
        }
        quickSelect(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr, k); // 返回前k个元素
    }

    private static void quickSelect(int[] arr, int left, int right, int k) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            if (pivotIndex == k - 1) {
                return; // 找到第k小的元素
            }
            if (pivotIndex < k - 1) {
                quickSelect(arr, pivotIndex + 1, right, k); // 在右半部查找
            } else {
                quickSelect(arr, left, pivotIndex - 1, k); // 在左半部查找
            }
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // 选择最后一个元素作为pivot
        int i = left;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, right); // 将pivot放到正确位置
        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int[] result = getLeastNumbers(arr, k);
        System.out.println(Arrays.toString(result)); // 输出：[1, 2]
    }
}

总结

在寻找最小k个数的问题中，我们可以使用多种方法来解决，选择合适的方法取决于数据的规模和特点。排序法简单易懂，但在大数据集时效率较低；堆法在内存使用上更为高效；快速选择算法虽然实现稍复杂，但在平均情况下性能优越。在实际开发中，理解这些算法的原理和适用场景是非常重要的。选择合适的算法可以大幅提高程序的执行效率和响应速度。