返回介绍

lcci / 17.14.Smallest K / README

发布于 2024-06-17 01:04:42 字数 3515 浏览 0 评论 0 收藏 0

面试题 17.14. 最小 K 个数

English Version

题目描述

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例:

输入: arr = [1,3,5,7,2,4,6,8], k = 4
输出: [1,2,3,4]

提示:

  • 0 <= len(arr) <= 100000
  • 0 <= k <= min(100000, len(arr))

解法

方法一:排序

直接排序,取前 k 个数即可。

时间复杂度 $O(n\log n)$。其中 $n$ 为数组长度。

class Solution:
  def smallestK(self, arr: List[int], k: int) -> List[int]:
    return sorted(arr)[:k]
class Solution {
  public int[] smallestK(int[] arr, int k) {
    Arrays.sort(arr);
    int[] ans = new int[k];
    for (int i = 0; i < k; ++i) {
      ans[i] = arr[i];
    }
    return ans;
  }
}
class Solution {
public:
  vector<int> smallestK(vector<int>& arr, int k) {
    sort(arr.begin(), arr.end());
    vector<int> ans(k);
    for (int i = 0; i < k; ++i) {
      ans[i] = arr[i];
    }
    return ans;
  }
};
func smallestK(arr []int, k int) []int {
  sort.Ints(arr)
  ans := make([]int, k)
  for i, v := range arr[:k] {
    ans[i] = v
  }
  return ans
}

方法二:优先队列(大根堆)

维护一个大小为 $k$ 的大根堆,遍历数组,将当前元素入堆,如果堆的大小超过 $k$,弹出堆顶元素。

遍历结束,将堆中元素的 $k$ 个元素取出即可。

时间复杂度 $O(n\log k)$。其中 $n$ 为数组长度。

class Solution:
  def smallestK(self, arr: List[int], k: int) -> List[int]:
    h = []
    for v in arr:
      heappush(h, -v)
      if len(h) > k:
        heappop(h)
    return [-v for v in h]
class Solution {
  public int[] smallestK(int[] arr, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
    for (int v : arr) {
      q.offer(v);
      if (q.size() > k) {
        q.poll();
      }
    }
    int[] ans = new int[k];
    int i = 0;
    while (!q.isEmpty()) {
      ans[i++] = q.poll();
    }
    return ans;
  }
}
class Solution {
public:
  vector<int> smallestK(vector<int>& arr, int k) {
    priority_queue<int> q;
    for (int& v : arr) {
      q.push(v);
      if (q.size() > k) {
        q.pop();
      }
    }
    vector<int> ans;
    while (q.size()) {
      ans.push_back(q.top());
      q.pop();
    }
    return ans;
  }
};
func smallestK(arr []int, k int) []int {
  q := hp{}
  for _, v := range arr {
    heap.Push(&q, v)
    if q.Len() > k {
      heap.Pop(&q)
    }
  }
  ans := make([]int, k)
  for i := range ans {
    ans[i] = heap.Pop(&q).(int)
  }
  return ans
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any)    { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文