java如何输出一个新数组，其中包含最多出现k次的前一个数组的所有数字

Question

如何创建一个新数组，其中包含java中最多出现k次的所有数组数

例如，如果数组为：

{1,4,4,3,4,3,5,2,5,1,5}

和k = 2，新数组将是：

{1,3,2}.

我假设我需要比较数组中的元素，并添加存储它作为变量出现的次数。然后我将该变量与k进行比较，如果它小于或等于它，它将把它添加到一个新的arraylist中。我真的不能实现这个想法。 谢谢

Answer 1

您至少有两种方法可以做到这一点：

1. 线性扫描数组，更新哈希表，该哈希表存储每个遇到数字的频率（平均时间：O（n），空间：O（n））
2. 对数组进行排序，并记录您看到当前元素的次数（每次当前数字与前一个不同时，将设置为1）。时间：O（n lg n），空间：O（m），其中m是返回元素的数量（假设使用O（1）空间复杂性分类器，如heapsort）

第一个是时间最优的，第二个是空间最优的

Answer 2

有很多方法可以做到这一点，这取决于您的约束是什么

如果您不需要担心内存限制，那么可以通过使用从数组元素映射到其频率的HashMap来非常轻松地解决这个问题。该算法通过扫描整个阵列来工作。对于每个元素，如果该元素已经在HashMap中，则更新HashMap中的键/值对以增加该元素的频率。否则，如果未看到元素，则将频率更新为1。填充完HashMap后，您可以遍历映射并将频率最多为k的所有元素复制到新的ArrayList。例如：

for(Map.Entry<T, Integer> entry: myMap.entrySet()) {
    if (entry.getValue() <= k)
        myArrayList.add(entry.getKey());
}

这在O（n）时间和O（n）内存中运行，这非常好

如果不想将所有内容都存储在内存中，另一个选项是使用Arrays.sort在O（n logn）时间和O（logn）空间中对数组进行排序。对数组进行排序后，每个值的所有副本都将连续存储，您可以更轻松地计算它们的频率。例如，在对您在原始帖子中提到的数组进行排序后，您将得到该数组

1 1 2 3 3 4 4 4 5 5 5

从这里可以更容易地确定每个元素有多少个副本。您可以通过遍历阵列来实现这一点，跟踪当前正在查找的元素以及有多少副本。每当看到新元素时，如果它与当前元素匹配，则递增计数器。如果不是，则将要检查的元素重置为新元素，并将计数器设置回1。例如，对于上面的数组，您可以从查看以下元素开始：

1 1 2 3 3 4 4 4 5 5 5
^

Element: 1
Frequency: 1

现在，看看数组的下一个元素。因为它是1，所以将频率计数增加到2：

1 1 2 3 3 4 4 4 5 5 5
  ^

Element: 1
Frequency: 2

当您查看下一个元素时，您将看到它是2。这意味着不再剩下1了。因为1有两个副本，所以可以将1追加到结果数组中。然后将计数器重置为1，保持此状态：

1 1 2 3 3 4 4 4 5 5 5
    ^

Element: 2
Frequency: 1

执行此操作时要注意的一件事是记住处理访问最终数组元素的情况。重要的是，当到达数组末尾时，如果最后一个元素最多有k个副本，则将最后一个数字添加到输出数组中

每当执行此操作时，如果发现一个元素最多出现k次，可以将其添加到新数组中。第二步在O（n）时间和O（m）空间中运行（其中m是结果数组中的元素总数），因此总复杂度是O（n logn）时间和O（m+logn）空间

希望这有帮助