算法的学习笔记—最小的 K 个数(牛客JZ40)

举报
尘觉 发表于 2024/08/27 14:41:30 2024/08/27
【摘要】 在编程面试中,找出一个数组中最小的K个数是一个常见的问题。虽然看似简单,但要在高效性方面有所保证却并不容易。本文将介绍两种有效解决该问题的算法:基于堆的解法和快速选择算法。我们将详细讲解它们的实现方式、时间复杂度分析以及适用场景,帮助你在面试中从容应对这一问题。

😀前言
在编程面试中,找出一个数组中最小的K个数是一个常见的问题。虽然看似简单,但要在高效性方面有所保证却并不容易。本文将介绍两种有效解决该问题的算法:基于堆的解法和快速选择算法。我们将详细讲解它们的实现方式、时间复杂度分析以及适用场景,帮助你在面试中从容应对这一问题。

最小的 K 个数

题目链接

牛客网

问题描述

给定一个长度为n的数组,数组中可能包含重复值。要求找出其中不去重的最小的k个数。例如,给定数组 [4,5,1,6,2,7,3,8]k=4,则返回 [1,2,3,4](任意顺序皆可)。

数据范围和要求

  • 数据范围:0≤k,n≤10000,数组中每个数的大小在0到1000之间。
  • 时间复杂度要求:O(nlogk)
  • 空间复杂度要求:O(n)

方法一:基于堆的解法

堆是一种适合处理部分排序问题的数据结构。在本题中,我们使用大顶堆来维护最小的k个数。

具体思路

  1. 创建一个大小为k的大顶堆,用于存储当前找到的最小的k个数。
  2. 遍历数组元素,将每个元素加入大顶堆。
  3. 如果堆的大小超过k,则将堆顶元素移除。堆顶元素是堆中最大的数,这样可以确保堆中存储的都是当前最小的k个数。

在Java中,我们可以使用PriorityQueue类实现堆,并在初始化时通过Lambda表达式(o1, o2) -> o2 - o1来构建大顶堆。

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
        // 如果k大于数组长度或k小于等于0,直接返回空的结果
        if (k > nums.length || k <= 0) {
            return new ArrayList<>();
        }
        
        // 创建一个大顶堆,用于存储最小的k个数
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        
        // 遍历数组中的每个元素
        for (int num : nums) {
            // 将元素加入大顶堆
            maxHeap.add(num);
            // 如果堆的大小超过k,移除堆顶元素(即最大元素)
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        
        // 将堆中的元素转为ArrayList返回
        return new ArrayList<>(maxHeap);
    }
}

时间复杂度分析

在此算法中,维护堆的插入和删除操作的时间复杂度为O(logk)。因此,遍历整个数组的时间复杂度为O(nlogk),最终的空间复杂度为O(k),这是由于堆的存储占用的空间。

适用场景

这种基于堆的解法特别适合处理大规模数据,尤其是当k较小且数据量n较大时,它的效率优势更加明显。

方法二:快速选择算法

快速选择算法基于快速排序的思想,通过分治法快速找到第k个最小的元素,并将前k个元素放在数组的前k个位置上。

具体思路

  1. 使用快速排序的partition()方法,将数组分割成两部分,其中一部分比选定的pivot小,另一部分比pivot大。
  2. 通过调整pivot的位置,可以快速定位到第k个最小的元素。
  3. 最终数组的前k个元素即为最小的k个数。

代码实现

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
        ArrayList<Integer> ret = new ArrayList<>();
        // 如果k大于数组长度或k小于等于0,直接返回空的结果
        if (k > nums.length || k <= 0) {
            return ret;
        }
        
        // 使用快速选择算法找到第k个最小元素
        findKthSmallest(nums, k - 1);
        
        // 将前k个元素加入结果列表
        for (int i = 0; i < k; i++) {
            ret.add(nums[i]);
        }
        return ret;
    }

    // 快速选择算法,找到数组中第k个最小的元素
    public void findKthSmallest(int[] nums, int k) {
        int l = 0, h = nums.length - 1;
        while (l < h) {
            // 调用partition方法对数组进行分区
            int j = partition(nums, l, h);
            // 如果找到的分区位置正好是k,则停止
            if (j == k) {
                break;
            }
            // 如果分区位置大于k,调整高位指针
            if (j > k) {
                h = j - 1;
            } else {
                // 如果分区位置小于k,调整低位指针
                l = j + 1;
            }
        }
    }

    // partition方法对数组进行分区,使得左边元素小于pivot,右边元素大于pivot
    private int partition(int[] nums, int l, int h) {
        int p = nums[l];  // 选取数组的第一个元素作为pivot
        int i = l, j = h + 1;
        while (true) {
            // 从左向右找到第一个大于pivot的元素
            while (i != h && nums[++i] < p);
            // 从右向左找到第一个小于pivot的元素
            while (j != l && nums[--j] > p);
            // 如果左右指针交错,退出循环
            if (i >= j) {
                break;
            }
            // 交换这两个元素的位置
            swap(nums, i, j);
        }
        // 最后将pivot放到正确的位置
        swap(nums, l, j);
        return j;  // 返回pivot的位置
    }

    // 交换数组中两个元素的位置
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

时间复杂度分析

快速选择算法的时间复杂度为O(n),空间复杂度为O(1),因为它直接在原数组上进行修改,而不需要额外的存储空间。

适用场景

这种方法在需要快速得到结果且允许修改数组的情况下非常有效。如果数组不可修改,建议使用堆的解法。

😄总结

通过对比,我们可以看到两种方法各有优劣。堆的解法适用于大规模数据和较小的k值场景,而快速选择算法在需要快速得到结果且允许修改数据时更加高效。根据具体需求选择适合的算法,能够更好地解决问题,提升面试表现。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。