向集合添加元素与在java中使用流的时间复杂度

Question

我在面试中被问到这个问题，计算二进制数组中的数字 1 和 0 例如：arr = 1, 1, 0, 1, 0, 1, 0, 0, 0。我们不应该使用Array.sort或collections.sort函数。 我可以考虑使用带有过滤器和计数操作的流作为一种方法，以及将元素添加到哈希图中并打印计数的另一种方法。

我读到过滤器将在内部使用迭代，最坏情况的时间复杂度是 o(n)。但对于 hashmap 来说，我们必须循环 array ，然后计算 hash 来添加元素。我想流将是一个更好的选择。 它是否正确。请说出您对这些的想法，如果有更好的方法请告诉我

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));

Answer 1

如果有更好的方法请告诉我

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

Map

数据结构存在大量开销，基于流的解决方案可能会在幕后涉及

Map

。

^{如果数组足够大，值得并行化，那么使用流将简化代码。但是，我不相信并行流解决方案会比带有两个计数器的简单非并行循环更快。}