0

给定一个大小为 100000 的数组arr，每个元素0 <= arr[i] < 100. （未排序，包含重复项）

找出存在多少个三元组(i,j,k)，使得arr[i] ^ arr[j] ^ arr[k] == 0 Note :^是 Xor 运算符。还0 <= i <= j <= k <= 100000

我有一种感觉，我必须计算频率并使用频率进行一些计算，但我似乎无法开始。

欢迎任何比显而易见的算法更好的算法O(n^3)。:)

这不是家庭作业。:)

4

6 回答 6

4

我认为关键是您不需要识别 i,j,k，只需数一下。

初始化一个大小为 100 的数组

通过 arr 循环，计算每个值有多少 - O(n)

循环遍历小数组的非零元素，找出满足条件的三元组 - 假设所涉及的三个数字的计数是 A、B、C - 原始 arr 中的组合数是 (A+B+C )/!A!B!C! - 100**3 次操作，但假设 100 是固定值，这仍然是 O(1)。

很快）。

于 2010-11-18T11:23:27.117 回答
1

可能的 O(n^2) 解决方案（如果可行）：维护变量count和两个数组，single[100]以及pair[100]. 迭代arr, 和 为 value 的每个元素n：

  • 更新count：count += pair[n]
  • update pair: 迭代数组single并为索引x和值的每个元素s != 0做pair[s^n] += single[x]
  • 更新single：single[n]++

最终count保持结果。

于 2010-11-18T11:49:45.737 回答
1

可能的 O(100 * n) = O(n) 解决方案。它解决了问题 i <= j <= k。如你所知 A ^ B = 0 <=> A = B，所以

long long calcTripletsCount( const vector<int>& sourceArray )
{
  long long res = 0;
  vector<int> count(128);
  vector<int> countPairs(128);
  for(int i = 0; i < sourceArray.size(); i++)
  {
    count[sourceArray[i]]++; // count[t] contain count of element t in (sourceArray[0]..sourceArray[i]) 
    for(int j = 0; j < count.size(); j++)
      countPairs[j ^ sourceArray[i]] += count[j]; // countPairs[t] contain count of pairs p1, p2 (p1 <= p2 for keeping order) where t = sourceArray[i] ^ sourceArray[j]
    res += countPairs[sourceArray[i]]; // a ^ b ^ c = 0 if a ^ b = c, we add count of pairs (p1, p2) where sourceArray[p1] ^ sourceArray[p2] = sourceArray[i]. it easy to see that we keep order(p1 <= p2 <= i)
  }  
  return res;
}

对不起，我的英语不好...

于 2010-11-18T13:05:30.847 回答
0 
Sort the array, keeping a map of new indices to originals. O(nlgn)
Loop over i,j:i<j. O(n^2)
  Calculate x = arr[i] ^ arr[j]
  Since x ^ arr[k] == 0, arr[k] = x, so binary search k>j for x. O(lgn)
  For all found k, print mapped i,j,k

O(n^2 lgn)

于 2010-11-18T11:18:52.590 回答
0

正如保罗建议的那样，从 1 到 100 之间的每个数字出现的频率计数开始。这将产生一个长度为 100 的数组 freq[]。

接下来，不是循环遍历该数组中的三元组 A、B、C 并测试条件 A^B^C=0，而是遍历 A < B 的对 A、B。对于每个 A、B，计算 C=A^B （所以现在 A^B^C=0），并验证 A < B < C < 100。（任何三元组都会以某种顺序出现，所以这不会错过三元组。但见下文）。运行总数将如下所示：

Sum+=freq[A]*freq[B]*freq[C]

频率计数的工作量为 O(n)，加上 A < B 上的循环大约为 5000。

由于三个不同数字 A、B、C 的每个三元组都必须以某种顺序出现，因此每个这样的三元组都恰好出现一次。接下来，您必须寻找两个数字相等的三元组。但是，如果两个数相等且其中三个的异或为 0，则第三个数必须为零。所以这相当于在频率计数数组上对 B 进行二次线性搜索，计算 (A=0, B=C < 100) 的出现次数。（在这种情况下要非常小心，尤其是在 B=0 的情况下要小心。计数不仅仅是 freq[B] ** 2 或 freq[0] ** 3。那里隐藏着一个小组合问题。）

希望这可以帮助！

于 2010-11-18T13:05:22.907 回答
0

我有一个（简单的）O(n^2 log n) 解决方案，它考虑到 i、j 和 k 指的是索引而不是整数的事实。

一个简单的第一遍允许我们构建一个包含 100 个值的数组 A：值 -> 索引列表，我们保持列表排序以备后用。O(n log n)

对于每对 i,j 使得 i <= j，我们计算 X = arr[i]^arr[j]。然后我们在 A[X] 中执行二分搜索来定位索引 k 的数量，使得 k >= j。O(n^2 日志 n)

我找不到任何方法来利用排序/计数算法，因为它们消除了索引要求。

于 2010-11-18T15:30:09.163 回答