arrays - 建议一个有效的算法

Question

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

找出有多少个三胞胎(i,j,k)存在使得arr[i] ^ arr[j] ^ arr[k] == 0注意:^是异或运算符。还有0 <= i <= j <= k <= 100000

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

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

这不是作业。 :)

Answer 1

我认为关键是你不需要识别 i,j,k，只需要数出有多少。

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

遍历 arr，计算每个值有多少 - O(n)

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

所以，O(n)。