问题概述

在一堆整数中，根据重复次数不同，找出某个特定重复次数的数。

问题分析

既然该问题的结果与数字的重复次数有关，那就一定要计数，普通的求解办法是将每个数看成一个整体进行计数，需要$O(n)$O(n)的空间复杂度。而另一个十分有趣的解法是考虑数在计算机里的二进制表示，将数分解到位，按位计数，可以将空间复杂度优化到$O(1)$O(1)。

问题详述及按位计数法概述

1. 问题详述
   给定n个整数，除了一个数字A的重复次数为y外，其余数字的重复次数均为x(x>1)的整数倍，显然y不是x的整除倍，问题就是找出这个数字A。
2. 算法概述
   考虑到整数在计算机中的二进制存储形式，盯住所有数的某一位，若A在这一位上为0，则所有数在这一位的和一定是x的整数倍；若A在这一位上为1，则所有数在这一位的和一定不是x的整数倍。由此便可确定A每一位的值，进而得到A。

算法详述

现在假设这n个数存放在32b的int型数组a[$0\cdots n-1$0⋯n−1 ]中，然后现在盯住a[i]这个整数的第$j(j\in [0,31])$j(j∈[0,31])位，记作 $a_{ij}$aij​。我们A的第j位记作$A_{j}$Aj​。我们将n个数上第j位的累加和记作$S_{j}$Sj​，即$S_{j}=\sum_{i=0}^{n-1}a_{ij}$Sj​=i=0∑n−1​aij​
有如下两种情况：

• 若$A_{j}=0，一定有S_{j}=k_{1}x,k_{1}\in N^{+}$Aj​=0，一定有Sj​=k1​x,k1​∈N+
• 若$A_{j}=1，一定有S_{j}=k_{1}x+y=k_{2}x+b,k_{2}\in N^{+}$Aj​=1，一定有Sj​=k1​x+y=k2​x+b,k2​∈N+
  即$S_j=\sum_{i=0}^{n-1}a_{ij}=\begin{cases} k_{1}x & k_{1}\in N^{+} \\ k_{2}x+b & k_{2}\in N^{+} \end{cases}$Sj​=i=0∑n−1​aij​={k1​xk2​x+b​k1​∈N+k2​∈N+​
  由上式可得$A_j=\frac{S_j\%x}{b}$Aj​=bSj​%x​
  故$A=\sum_{j=0}^{31}A_j\cdot 2^j$A=j=0∑31​Aj​⋅2j

算法实现

1. 按位直接计数法，需要知道存储数据的整型类型的位数，下面以32位为例，伪代码如下：

S[32] = {0}
for(i = 0; i < n; i++){
	for(j = 0; j < 31; j++){
        if(a[i] & 1<<j){
            S[j] = (S[j] + 1)%x;//对a数组第j位进行计数
        }
    }
}
A = 0;
for(j = 0; j < 31; j++){
    if(S[j] > 0){
        A |= 1<<j;//将A的第j位置1
    }
}

2. 真值表法实现自动计数，可以进一步优化空间复杂度，而且不需要知道整型位数。重复5的倍数找3次的c语言实现如下：

#include<stdio.h>
int singleNumber(int *arry, int len){
	const int *a = arry;
	int p=0,q=0,r=0;
	int old_p,old_q,old_r;//临时变量 
	for(int i = 0; i < len; i++){
		old_p = p;
		old_q = q;
		old_r = r;
		p = (old_p&~old_q&~old_r&~a[i])|(~old_p&old_q&old_r&a[i]);
		q = (~old_p&old_q&~a[i])|(~old_p&a[i]&(old_q^old_r));
		r = ~old_p&(old_r^a[i]);
	}
	return r;
}

int main(){
	int a[13] = {5,5,5,2,2,7,7,7,7,7,2,5,5};
	printf("%d\n",singleNumber(a,13));
	return 0;
}

真值表法详述：

真值表在本题中的表现，着实让我惊艳了一下。用真值表我们可以实现我们自定义的运算规则。
分析讲解：如果用二进制数来当计数器，那么计数x次，最少需要m位二进制数。
$x,m满足：2^{m-1}&lt;x\le 2^m$x,m满足：2m−1<x≤2m
则我们需要m个int型变量，用m个变量对应的第j位逻辑上组成一个m位的计数器，记作$S_j$Sj​。
计数器根据输入$a_{ij}$aij​的计数规律为：$S_j=(S_j+a_{ij})\%x$Sj​=(Sj​+aij​)%x，但是该计数规律并非是用加法和取余实现的，而是通过真值表得到的位运算实现的。计数结束后，m个变量的值要么是结果A，要么是0。
以重复5的倍数找3次为例，需要3个int型变量，3个变量的对应第j位组成一个3位计数器。计数器的计数过程为：
$000\longrightarrow^1001\longrightarrow^1010\longrightarrow^1(011)\longrightarrow^1100\longrightarrow^1000$000⟶1001⟶1010⟶1(011)⟶1100⟶1000
我们分别用p，q，r来表示计数器的3个位，input相当于$a_{ij}$aij​，则最后计数结束后，p位对应的变量值为0，而q，r对应的变量为结果A。
用真值表方法求解：

p	q	r	input	P	Q	R
0	0	0	0	0	0	0
0	0	1	0	0	0	1
0	1	0	0	0	1	0
0	1	1	0	0	1	1
1	0	0	0	1	0	0
0	0	0	1	0	0	1
0	0	1	1	0	1	0
0	1	0	1	0	1	1
0	1	1	1	1	0	0
1	0	0	1	0	0	0

我们根据当前的p,q,r与输入input经过某种关系映射后得到P,Q,R，所以理论上因变量P,Q,R的自变量为p,q,r,input。
如下所示：
$P=f(p,q,r,input)$P=f(p,q,r,input)
$Q=g(p,q,r,input)$Q=g(p,q,r,input)
$R=\varphi(p,q,r,input)$R=φ(p,q,r,input)
即

以上是一位的计数运算，而所有位的运算都是相同的。
实际编程中p,q,r,input都是32位int型变量，因为计算机中的位运算就是对变量进行按位的统一的位运算，即对变量的所有位进行相同的运算，故而上述算法不用分解到位，单独运算，再进行整合。
不过对于不同的重复次数需要画不同的真值表，然后再算计数表达式，没有统一的公式。

如果没有对效率有特别严格的要求，建议使用方法一。另外重复2的倍数找一次，使用异或运算即可，也属于真值表法，不过这种情况比较好记。