3

我有一个巨大的 int 数组，我需要找到它的模式，

我见过一些使用 2 个for循环（一个嵌套）的方法，这似乎是不必要的。

我认为找到只有一个循环的模式的唯一方法是使用Maps：

int[] elements = new int[]{....numbers...};
Map<Integer,Integer> map = new .....Map Type....;
for(int number : elements){
    if(map.containsKey(Integer.valueOf(number))){
        map.put(Integer.valueOf(number),map.get(Integer.valueOf(number))+1);
    }else{
        map.put(Integer.valueOf(number),1);
    }
}

我不确定使用地图实际上会带来什么样的速度优势。有没有更好的方法？

4

3 回答 3

5

如果使用哈希映射，算法的运行时复杂度应该是 O(n)：你访问 n 个元素中的每一个一次，并且 HashMap 查找和写入通常假定为 O(1)。所以总共你得到O（n * 1），即O（n）。如果你使用树形图，你会得到 O(n log n)。

与两个嵌套循环（听起来像 O(n²)）相比，速度提升是从二次到线性的，这非常好：对于 1000 个元素，您执行 1000 个“步骤”而不是 1,000,000。

PS 在这里变得比线性更好可能很难 - 无法想象一种在不访问每个元素至少一次的情况下计算它的方法。

于 2013-11-09T13:35:21.163 回答
5

正如 Stefan Haustein 已经写的那样，使用 map 的复杂性远低于使用 2 个 for 循环。

如果您知道存储在数组中的数字范围，则可以进行进一步的改进或更专业化。例如，如果您计算 0-255 范围内的颜色，则不必使用地图，而是可以使用简单的数组。

int[] elements = new int[]{....numbers...};
int[] histogram = new int[256]; // 255 = highest possible value in elements
for(int number : elements){
  ++histogram[number];    
}

使用地图是一种更通用的方式。您可以将地图视为具有更复杂索引功能的数组。因此，在普通数组中，数字在array pointer + index地图中，这是使用线性哈希函数计算的。

于 2013-11-09T13:52:25.137 回答
0

没有算法可以比 O(n) 更快（请查看 wikipedia page for big-o notation）。至少，不一致（在所有可能的输入中）。这并不意味着它不能更快​​ - 只是，超过一定的问题规模，任何更快的速度都不能继续增加速度差异超过（可能很小的）线性因子。

这是因为，无论您检查元素的顺序如何，给定一个与获胜者“几乎平衡”的数组，您检查的最后一个元素可能会成为决胜局。给我任何不查看所有元素的算法，我可以编写一个输入数组，使其返回不正确的结果。因此，您必须至少检查一次所有这些：O(n) 复杂度。

Hashmap 具有 O(1) 的一般插入和查找复杂性——也就是说，平均而言，无论数据大小如何，它们都会花费恒定的时间来完成它们的工作。请注意，这个恒定时间比数组更新/查找大几倍（参见TwoThe的答案）。因此，除了常量（将根据 hashmap 实现、机器、VM 等而有所不同）之外，您不会比您发布的代码快得多。如果你真的需要 10% 的额外性能，那么在硬件/软件/输入数据上建立一个尽可能接近你预期部署的基准并优化它。

于 2013-11-09T14:02:11.817 回答