0

输入：一个未排序的整数数组A[1..n]，只有O(d) :(d < < n)不同的元素。

输出：所有恰好出现两次的元素。

要求两种算法，一种是 with O(Nd)，另一种是O(Nlogd)。最大数量可能非常大，因此n计算频率的大小数组可能不是一个好主意。任何想法？

澄清一下，“只有O(d) :(d < < n)不同的元素”是指所有其他元素（不是那些元素O(d)）出现两次或更多。

4

3 回答 3

1

O(nd)基本上是迭代所有可能的元素（O(d)其中的）并计算它重复的次数。每次迭代都是 O(n)

O(nlogd)是建立一个直方图( map:int->int)，计算每个元素在单次迭代中出现在列表中的次数。该映射是基于平衡二叉搜索树的，以确保O(nlogd)。请注意，如果您使用哈希映射而不是树，则可以将其增加到O(n)平均情况（但O(nd)最坏情况）

伪代码- O(nlogd)：

map <- new tree map
for each element x in list:
 if x is in map:
     map.put(x,map.get(x)+1)
 else:
     map.put(x,1)
for each (key,value) in map:
  if value == 2:
     print key
于 2013-01-03T11:06:43.577 回答
0

解决方案一 O(N * d)

  1. 找出数组中所有值等于 A[0] 的元素，计算个数。如果数字 == 2，请将其添加到答案中。最后，从数组中擦除所有选定的元素。
  2. 擦除所有相同的值元素会导致O(N)复杂度，这一步应该做d次，所以复杂度是O(N * d)。

解决方案二 O(N * logd)

使用平衡树计算所有值的频率。因为只有 d 个 dinstinct 值，所以树的大小只有 d，所有对它的操作都会被记录。我们将所有元素插入到树中，并计算树中节点的频率，总复杂度为 O(N * logd)。

C++ code:

vector<long long> solve()
{
    vector<long long> ans;
    map<long long, int> cnt;
    for(int i = 0; i < n; ++i)
        cnt[a[i]] += 1; // O(logd)
    for(map<long long, int>::iterator it = cnt.begin(); it != cnt.end(); ++it)
        if(it -> second == 2) ans.push_back(it -> first);
    return ans;
}
于 2013-01-03T11:15:19.113 回答
0

对数组进行排序。O(nlogn) 扫描数组以找到只出现两次的元素。O(n)

重复元素将并排排列。

O(n)+O(nlogn)。

于 2013-01-03T11:05:24.037 回答