查找列表中存在超过k次的所有元素的最佳方法

Question

我刚遇到问题，我想知道什么是解决此问题的最佳方法。

我列出

L = [[1, 2, 3, 4, 5, 6, 7], [2, 4, 6, 8, 10, 12], [3, 6, 9, 12, 15], ....] 

假设大号大小的列表ñ，这将是找到所有存在于ķ次以上元素的最佳途径L？

例如，如果k = 2，那么我应该得到 [2, 3, 4, 6, 12]。

Answer 1

假设L的大小是n，找到L中出现k次或更多次的所有元素的最佳方法是什么？

传统的方法是遍历每个列表一次，并收集HashMap<Integer, Integer>（其中键是一个数字，价值是次）的时间值。然后你只需要收集从地图的所有功能按键值k以上：

public static List<Integer> getResultListByMap(List<List<Integer>> inputList, int k) { 
    Map<Integer, Integer> times = new HashMap<>(); 
    for (List<Integer> integers : inputList) { 
     for (Integer integer : integers) { 
      if (times.keySet().contains(integer)) { 
       times.put(integer, times.get(integer) + 1); 
      } else { 
       times.put(integer, 1); 
      } 
     } 
    } 

    List<Integer> result = new ArrayList<>(); 
    for (Map.Entry<Integer, Integer> entry : times.entrySet()) { 
     if (entry.getValue() >= k) { 
      result.add(entry.getKey()); 
     } 
    } 
    return result; 
} 

result列表包含在列表k次以上

UPDATE提出的所有数字： OK，我已经知道你已经使用HashMap的方法，对你来说很慢。我写了与Java 8个流API功能的算法使用列表拼接，分拣和并行获得奖金：

public static List<Integer> getResultListBySort(List<List<Integer>> inputList, int k) { 
    List<Integer> newList = inputList.parallelStream() 
      .flatMap(l -> l.parallelStream()).sorted().collect(Collectors.toList()); 

    List<Integer> result = new ArrayList<>(); 

    Integer prev = null; 
    int sum = newList.get(0); 
    for (Integer integer : newList) { 
     if (integer.equals(prev)) { 
      sum++; 
     } else { 
      if (sum >= k) { 
       result.add(integer); 
      } 
      sum = 1; 
     } 
     prev = integer; 
    } 
    return result; 
} 

它是快了两倍多为2000 x 2000问题大小 - 2000名名单与2000元（现在只需要一半第二个让我的电脑上的结果列表）

Benchmark      Mode Samples Score Score error Units 
c.c.b.MyBenchmark.testMap  avgt  20 0,972  0,030 s/op 
c.c.b.MyBenchmark.testSorted avgt  20 0,534  0,005 s/op 

Answer 2

这完全取决于对L.执行的操作的频率，考虑你在一段时间曾经这样操作，它的优良找到带O的结果（ n_1 + n_2 + n_3 + ... + n_n）时间复杂度。即每次通过遍历数组和数组来迭代查找。如果这是一个频繁的操作，为什么不排序数组数组或为什么不使用缓存。我相信最好的方式完全取决于你的使用。

Answer 3

保持一个额外的计数数组，存储完全遍历的元素数。然后，遍历列表，同时更新元素的数量，并在更新元素的数量是否等于k时，将其添加到最终答案列表中，该列表最初为空。但为了这个工作，你应该知道给定数组中的最大元素。

final_answer = [] 
count = [0 for i in range(max_el)] # put very large number here e.g. 1000 
for sublist in L: 
    for element in sublist: 
     count[element] += 1 
     if count[element] == k: 
      final_list.append(element) 

打印（final_answer）