【每日打卡】[剑指offer]面试题40-最小的k个数

马谦马谦马谦 2020年3月20日21:31:33 发表评论

一、题目描述

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

示例 1:

  • 输入:arr = [3,2,1], k = 2
  • 输出:[1,2] 或者 [2,1]

示例 2:

  • 输入:arr = [0,1,2,1], k = 1
  • 输出:[0]

限制:

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

二、题解

解法一:排序

一个最简单的思路是先对所有元素排序,然后输出前面k个元素。使用快速排序的话,时间复杂度O(nlog(n))。

解法二:时间复杂度为O(n)的快速排序

快速排序的特点是:每次排序后,标杆元素左边的元素都比它小,右边的元素都比它大。因此可以利用这一个特性,对数组中的元素进行部分排序,直到返回的标杆元素下标等于k,那么这个标杆元素的左边就是所有需要的目标数据。

相较于快排来说,只需要对目标区间(标杆元素左边或者右边)进行排序就行了,无需对左右两边的区间都进行排序。因此时间复杂度降为O(n)。

解法三:最大堆

最大堆的性质是:堆上层的元素都大于等于下层元素。因此,只要维护一个大小为k的最大堆,循环遍历数组,如果元素大于堆顶元素,就替换掉堆顶元素,重新建堆。堆里面保存的就是k个最小的元素了。时间复杂度O(nlog(k)),空间复杂度O(k)。

三、代码:

3.1 基于快排思想的算法

【每日打卡】[剑指offer]面试题40-最小的k个数

3.2 使用最大堆

【每日打卡】[剑指offer]面试题40-最小的k个数

本文共执行63次查询,耗时0.351秒!
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: