2

我有一组数字说：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 元素复制到临时数组（向量）

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

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

4

1 回答 1

0

O(n)平均时间和O(k)空间解决方案可以是构建一个基于哈希的直方图，并迭代数组，同时为每个子列表中的元素维护#occurances。
在每次迭代中，踢出最老的元素（通过减少直方图中的相关入口）并添加一个新元素。
还要维护一个numDupes变量，该变量计算您当前拥有的重复对象数量，并在从当前候选对象中添加/删除元素时进行维护。

伪代码（对不起，如果我有 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 时删除元素。

于 2012-10-14T14:49:59.153 回答