给定一个整数数组，其中一些数字重复1次，一些数字重复2次，只有一个数字重复3次，你如何找到重复3次的数字。不允许使用哈希。算法的复杂度应为O（n）
我假设数组没有排序，或者类似，重复的数字不会出现在一个连续的运行中。否则，问题实际上是微不足道的：只需使用大小为3的窗口扫描数组一次，如果该窗口中的每个数字相同，那么这是在一次连续运行中重复3次的数字。
如果重复分散，则问题变得更加有趣。
由于这是家庭作业，我只会给你一个提示。
这个问题是你给出一个未排序整数数组的表兄弟，所有数字都出现偶数次，除了出现奇数次的数字。
通过对阵列中的所有数字执行异或，可以很容易地在O(N)中找到该数字;结果是出现奇数次数。
这有效的原因是x xor x = 0。
例如，3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7。
这个算法看起来很不错....但我不知道它的实现..只有伪代码....如果any1好试试他的代码（C编程），那么请发布它....
PseudoCode在这里...取两个大小为n的bitset数组。我们可以使用这个数组来计算最多三次出现，即如果array1 [i] = 1且array2 [i] = 1，那么这意味着我们有三次出现的第i + 1个元素。
对于每个整数'i'如果（array2 [i] == 1）array2 [i] = 0，array1 [i] = 1; else array2 [i] = 1;
对于数组中的每个元素K if（array1 [k] && array2 [k]）返回k;
复杂度= O（n）和空间= 2n位。
我将提出一个通用的解决方案，这样一个数字出现m次，其他n次。
我们需要一个运算符来取消n出现的整数，但保持m的出现。如果我们将每个数字转换为其二进制表示，并且对于每个位位置，计算该位设置的次数，对于发生n次数的所有数字，该值将是n的倍数，加上相应的0或m一个整数的位。
如果我们取这些计数中的每一个的模数n，并除以m，则结果是单个整数的相应位位置的值。剩下的就是将二进制结果转换为十进制正式。
For example, given array = [3, -4, 3, 3], m = 1 and n = 3:
Binary of 3 = 011
Binary of -4 (2s complement) = 11111111111111111111111111111100
Bit 0: 3 % 3 = 0
Bit 1: 3 % 3 = 0
Bit 2 through 32: 1 % 3 = 1
The result is -4
void main()
{
int a[10]={1,5,2,8,5,9,0,5,3,7}, n, i, j, k=0;
int p;
printf("\n");
for(i=0; i<10; i++)
{
p=1;
for(j=i+1; j<10; j++)
{
if(a[i]==a[j])
p++;
}
if(p==3)
{
printf("the no is: %d",a[i]);
getch();
exit(0);
}
}
printf("not available\n");
getch();
}
使用基数排序（指定整数所需的位数是线性的），然后扫描三元组。
这是一个假设max（A）相当小的答案，其中A是输入数组：
int ValidCount(int[] a, int[] b, int i, int n) {
int num = a[i];
int ret = 0;
if (b[3*num] >= 0 && b[3*num] < n && a[b[3*num]] == num) ret++;
if (b[3*num+1] >= 0 && b[3*num+1] < n && a[b[3*num+1]] == num) ret++;
if (b[3*num+1] >= 0 && b[3*num+2] < n && a[b[3*num+2]] == num) ret++;
b[3*num+ret] = i;
return ++ret;
}
int threerep(int[] A, int aSize) {
int *B = malloc(sizeof(int) * 3 * max(A, aSize)); /* Problematic if max(A) is large */
/* Note that we don't rely on B being initialized before use */
for(int i = 0; i < aSize; i++) {
if (ValidCount(A, B, i, aSize) == 3) return A[i];
}
return ERROR_NO_ANSWER;
}
本质上，问题是计算数组的模式。如果数组范围为[0，n-1]，则此解决方案仅“工作”。把解决方案放在这里，因为问题没有提出范围的条款。
这是带O（1）空间的O（n）（但带有范围子句）。
我不知道在O（n），O（1）中计算模式的任何算法，并且该范围没有子句。
我所能想到的就是这个，但我确信你的教授正在寻找一个棘手的方程式，可以在1次扫描中解决这个问题。您可以在2次扫描中执行此操作，即O（n），假设您可以创建第二个数组（第一个数组中的0到最大数字）。扫描一次，找到数组中的最大数量。创建该大小的第二个数组。使用第二个数组作为桶再次迭代第一个数组，以增加第一个数组中每个元素的计数。将桶增加到3后，这就是您的解决方案。不是最好的，但在某些情况下会起作用。
我没有看到所有的大惊小怪：使用python 2.6和一个简单的函数，它超过列表，计算出现，一旦它找到一个发生3次的数字，返回它。
>>> def find3(l):
from collections import defaultdict
d = defaultdict(int)
for n in l:
d[n]+=1
if d[n] == 3:
return n
>>> print find3([1,1,1,2,3,4,5,6,7])
1
>>> print find3([1,1,2,3,4,5,6,7,5])
None
>>> print find3([1,1,2,3,4,5,6,7,5,4,5,5])
5
Bugaoo的算法看起来很整洁，引用如下。实际上，我们可以通过在“第一次传递”之前执行额外传递来概括它来找到min（A）和max（A）以及另一个额外的传递来将A中的每个元素移动到min（A）和max（A）的范围内，即A [0] -min（A）。在“第一次通过”和“第二次通过”之后（注意我们应该通过max（A）-min（A）而不是n来修改元素），我们可以将min（A）添加到最后找到的重复数字。
本质上，问题是计算数组的模式。如果数组范围为[0，n-1]，则此解决方案仅“工作”。把解决方案放在这里，因为问题没有提出范围的条款。假设'n'是数组的大小，扫描数组并标记A [A [i]] = A [A [i]] + n ----->第1遍将每个数组元素除以'n'，即A [i] = A [i] / n ---->第二遍第二遍中具有最大值的元素就是答案。这是带O（1）空间的O（n）（但带有范围子句）。我不知道在O（n），O（1）中计算模式的任何算法，并且该范围没有子句。
如果您知道整数序列的最小值和最大值并且min> = 0，则创建一个用零填充的数组[min，max]。扫描给定的数组，如果发生，则将第i个位置递增1。完成后，您在第二个数组中有频率表，其中数组位置指向一个整数。
int count[2^32];
for x in input:
count[x] = 0; // delete this loop if you can assume ram is cleared to 0.
for x in input:
count[x]++;
for x in input:
if count[x] == 3:
return x
请原谅各种语言:-)另外，拥有一个可以用任何整数索引的数组真是太愚蠢 - 你可以在64位系统上完成它并且它确实符合要求。