algorithm - 检测给定数字列表的子集中的重复元素

Question

我有一组数字说:1 1 2 8 5 6 6 7 8 8 4 2...

我想检测上述数字的子数组(给定大小，比如 k)中的重复元素...例如:考虑 k=3 的递增子数组`

Sub array 1 :{1,1,2}
Sub array 2 :{1,2,8}
Sub array 3 :{2,8,5}
Sub array 4 :{8,5,6}
Sub array 5 :{5,6,6}
Sub array 6 :{6,6,7}
....

所以我的算法应该检测到子数组 1、5 和 6 包含重复项。我的方法:

1)复制前k个元素到一个临时数组(vector)

2) 在 C++ STL 中使用#include 文件...使用 unique() 我会确定向量的大小是否有任何变化..

关于如何解决这个问题的任何其他线索......因为如果给定数字的列表很大，我的方法会消耗大量时间和空间......

Answer 1

O(n) 平均时间和 O(k) 空间解决方案可能是构建一个基于散列的 histogram ，并在维护每个子列表中元素的 #occurances 的同时迭代数组。
在每次迭代中，踢出最老的元素(通过减少直方图中的相关入口)并添加一个新元素。
同时维护一个 numDupes 变量，它计算你当前有多少个 dupes，并在从当前候选人中添加/删除元素时维护。

伪代码(抱歉，如果我有 1 个错误或其他原因，但这是想法):

numDupes = 0
histogram = new map<int,int>;
//first set:
for each i form 0 to k:
  if histogram.contains(arr[i]):
     histogram.put(arr[i],histogram.get(arr[i]) + 1)
     numDupes += 1
  else:
     histogram.put(arr[i],1)
//each iteration is for a new set
if (numDupes > 0) print 1 //first sub array has dupes
for each i from k to n:
   if (histogram.get(arr[i-k]) > 1) numDupes -= 1 //we just removed a dupe
   histogram.put(arr[i-k],histogram.get(arr[i-k] - 1)) //take off "eldest" element.
   if (histogram.contains(arr[i]) && histogram.get(arr[i]) > 0):
       histogram.put(arr[i],histogram,get(arr[i]) + 1))
       numDupes += 1 //we just added a dupe
   else:
       histogram.put(arr[i],1)
   if (numDupes > 0) print i-k+1 // the current sub array contains a dupe

---

最初的答案有一个小错误:当添加的最后一个元素没有导致欺骗时，它无法捕捉到情况，但仍然有一个(如示例中的子数组 6)。
它可以通过维护一个额外的整数来解决，该整数计算当前找到的重复项的数量，并在计数器大于 0 时打印子数组。(更新了伪代码)。

另请注意:要实现 O(k) 空间，您的 histogram 需要删除值为 0 的元素。