6

问题是从在列表中查找单个数字扩展而来的

如果我将问题扩展到此：在所有其他数字恰好出现 k 次的列表中查找仅出现一次的数字的最佳算法是什么？

有人有好的答案吗？

例如，A = { 1, 2, 3, 4, 2, 3, 1, 2, 1, 3 }，在这种情况下，k = 3。如何获得 O(n) 中的单个数字“4”时间和空间复杂度是O(1)？

4

5 回答 5

4

如果数组中的每个元素都小于 n 且大于 0。
设数组为 a，遍历数组以获取每个a[i]add nto a[(a[i])%(n)]。
现在再次遍历数组，a[i]小于2*n和大于的位置n（假设基于 1 的索引）就是答案。

如果至少一个元素大于 n，则此方法将不起作用。在这种情况下，您必须使用 Jayram 建议的方法

编辑：
要检索数组，只需应用于数组mod n中的每个元素

于 2013-10-30T06:21:15.483 回答
2

如果通过对所有数字执行操作，除数字以外的数字lonely number恰好以偶数计数（即 2、4、6、8...）出现，则可以在给定的约束条件下解决此问题。XOR但除了空间复杂性之外，O(1)它只是在取笑我。

如果不是您给定的限制，您可以使用这些方法来解决这个问题。

  1. 对数字进行排序并使用当前变量来获取当前数字的计数。如果大于 1，则转到下一个数字，依此类推。空间 O(1)...时间 O(nlogn)
  2. 使用 O(n) 额外内存来计算每个数字的出现次数。时间 O(n)...空间 O(n)
于 2013-10-30T06:04:27.653 回答
0

根据banarun解决方案（带有小修复）：

算法条件：

 for each i arr[i]<N (size of array)
 for each i arr[i]>=0 (positive)

算法：

int[] arr = { 1, 2, 3, 4, 2, 3, 1, 2, 1, 3 };
for (int i = 0; i < arr.Length; i++)
{
    arr[(arr[i])%(arr.Length)] += arr.Length;
    if(arr[i] < arr.Length)
        arr[i] = -1;
}
for (int i = 0; i < arr.Length; i++)
{

     if (arr[i] - 3 * arr.Length <0 && arr[i]!=-1)
          Console.WriteLine("single number = "+i);
}

该解决方案具有 O(N) 的时间复杂度和 O(1) 的空间复杂度

注意：同样，只有当所有数字都是正数并且所有数字都小于 N 时，此算法才能工作。

于 2013-10-30T08:42:20.247 回答
0

这是一种机制，它可能不如其他机制好，但它具有指导意义，并深入了解了为什么 XOR 答案与 k = 2 时一样好的核心。

1. Represent each number in base k. Support there are at most r digits in the representation
2. Add each of the numbers in the right-most ('r'th) digit mod k, then 'r - 1'st digit (mod k) and so on
3. The final representation of r digits that you have is the answer.

例如，如果数组是

A = {1, 2, 3, 4, 2, 3, 1, 2, 1, 3, 5, 4, 4}

mod 3中的表示是

A = {01, 02, 10, 11, 02, 10, 01, 02, 01, 10, 12, 11, 11}

r = 2
Sum of 'r'th place = 2
Sum of the 'r-1'th place = 1

因此答案 ={12} in base 3这是5。

这是一个答案O(n * r)。注意与r成正比log n。

为什么 XOR 答案在 中O(n)？因为处理器提供了一个 XOR 操作，它是O(1)及时执行的，而不是O(r)我们上面提到的因素。

于 2013-10-30T20:43:14.907 回答
0

我只想扩展@banarun answer。

将输入作为 map 。喜欢a[0]=1; 然后将其视为myMapas 0index 和1as value 。

并在读取输入时找到最大数 M 。然后找到A大于MP 的素数。

不遍历地图，如果未启动add to的每个键i，请将其设置为。现在再次遍历And是您的答案的位置。基本上这个想法是从 banarun 建议的 Algo 中删除溢出和覆盖问题。myMapPmyMap(myMap(i)%P)myMap(myMap(i)%P)PmyMapmyMap[i] is >=P< 2*P

于 2013-10-30T07:24:53.153 回答