代码之家 › 专栏 › 技术社区 › flash

前k个常用元素

data-structures algorithm java

flash · 技术社区 · 6 年前

我正在处理一个面试问题,在这个问题中,我需要返回k个最常用的元素,给出一个非空整数数组。

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

这是我的代码:

  public static void main(String[] args) {
    System.out.println(topKFrequent(new int[] {1, 1, 1, 2, 2, 3, 3}, 1));
  }

  private static List<Integer> topKFrequent(int[] nums, int k) {
    // freq map
    Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
    for (int n : nums) {
      freq.put(n, freq.getOrDefault(n, 0) + 1);
    }
    // bucket sort on freq
    List<Integer>[] bucket = new LinkedList[nums.length + 1];
    for (int i = 0; i < bucket.length; i++)
      bucket[i] = new LinkedList<>();
    for (int key : freq.keySet()) {
      bucket[freq.get(key)].add(key);
    }
    // gather result
    List<Integer> res = new ArrayList<>();
    for (int i = bucket.length - 1; i >= 0; i--) {
      res.addAll(bucket[i]);
      if (res.size() >= k)
        break;
    }
    return res;
  }

我想检查这段代码是否有任何改进/优化?当存在多个频率相同的数字时,我会感到困惑。在那种情况下我们该怎么办?

1 回复 | 直到 6 年前

Valentin Carnu 6 年前

这一部分

List<Integer>[] bucket = new LinkedList[nums.length + 1];
for (int i = 0; i < bucket.length; i++)
  bucket[i] = new LinkedList<>();
for (int key : freq.keySet()) {
  bucket[freq.get(key)].add(key);
}

我只写一个循环

List<Integer>[] bucket = new LinkedList[nums.length + 1];
for (int key : freq.keySet()) {
  List<Integer> currentBucket = bucket[freq.get(key)];
  if (currentBucket == null) {
      currentBucket = new LinkedList<Integer>();
      bucket[freq.get(key)] = currentBucket;
  }
  currentBucket.add(key);
}

在这种情况下,最后一部分

List<Integer> res = new ArrayList<>();
for (int i = bucket.length - 1; i >= 0; i--) {
  res.addAll(bucket[i]);
  if (res.size() >= k)
    break;
}

需要跳过空值

List<Integer> res = new ArrayList<>();
for (int i = bucket.length - 1; i >= 0; i--) {
  if (bucket[i] == null) {
      continue;
  }
  res.addAll(bucket[i]);
  if (res.size() >= k)
    break;
}

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前