Java统计二进制数组0/1数量：Stream与HashMap的时间复杂度对比及最优方案

你的判断是否正确？ #

你的判断不完全准确。虽然Stream的filter+count操作时间复杂度为O(n)，但Stream框架本身存在额外的封装开销（比如流实例的创建、Lambda表达式的调用），在实际运行时，尤其是处理大规模数组时，其性能可能不如HashMap实现。

而HashMap实现中，由于数组元素只有0和1两种，哈希计算几乎没有冲突，存取操作的开销极低，实际运行效率反而更稳定。不过这两种方法都不是最优解。

更高效的解法：双计数器遍历 #

因为数组元素仅包含0和1，我们可以直接用两个计数器变量，遍历数组一次即可完成统计。这种方法时间复杂度O(n)，空间复杂度O(1)，是性能最优的方案——既不需要Stream的框架开销，也不需要HashMap的哈希存储开销，完全是原生的遍历操作。

各解法代码示例 #

1. Stream实现

int[] array = new int[]{1, 1, 0, 1, 0, 1, 0, 0, 0};
long zeroCount = Arrays.stream(array).filter(num -> num == 0).count();
long oneCount = array.length - zeroCount;
System.out.println("0: " + zeroCount);
System.out.println("1: " + oneCount);

2. 你提供的HashMap实现

int[] array = new int[]{1, 1, 0, 1, 0, 1, 0, 0, 0};
// find count of one and zero
Map<Integer,Integer> integerMap = new HashMap<>();
for(int i : array){
   if(integerMap.containsKey(i)){
       integerMap.put(i, integerMap.get(i) + 1);
   } else {
       integerMap.put(i,1);
   }
}
integerMap.forEach((key, value) -> System.out.println(key + " " + value));

3. 最优双计数器实现

int[] array = new int[]{1, 1, 0, 1, 0, 1, 0, 0, 0};
int zeroCount = 0;
int oneCount = 0;
for (int num : array) {
    if (num == 0) {
        zeroCount++;
    } else {
        oneCount++;
    }
}
System.out.println("0: " + zeroCount);
System.out.println("1: " + oneCount);

内容的提问来源于stack exchange，提问作者Mausumi