待字闺中：数组类题目之统计数字出现次数【存疑】【20131006更新】

By arthur503 -- 05 Oct 2013

看@陈利人老师的微信号“待字闺中”，有一段时间连续好几道数组题，把数组的各个思考方向都涵盖到了，所以萌生出总结一下的念头。主要是看看数组类题目的解题思路有哪些方向，分别适用于哪些场景。题目会一道道分析，慢慢添加的。

本来预计的是分数组类和字符串类两篇来写。但根据目前做的情况，数组类下面也分好多子分类，包括：统计数字出现次数、寻找特殊子串（如等差数列等）、数字排序等，因此，可能还会多写几篇。

Ex0911：找数字续

一个数组A，数字出现的情况，只有以下三种：一些数字只出现一次；一些数字出现两次；只有一个数字出现三次。请给出方法，找到出现三次的数字。关注微信公众账号“待字闺中”，了解更多。

根据“先实现，后优化”的原则，我们先把最简单明显的思路列出来，之后再往下延伸，谈优化和最佳方案。

我想到的解决方法如下：

/**
 * 法一：使用HashMap存储，之后遍历元素找到count为3的数字。
 * 
 * 优点：万金油方法，适用范围广，可以用来找count为任意值的数字。
 * 		若需要查找操作，时间复杂度O(1)。
 * 缺点：需要占用额外空间。
 * 复杂度：空间复杂度O(n)，时间复杂度O(n)。
 */

/**
 * 法二：使用2位的bitmap存储，之后遍历找到count为3的数字。
 * 由于最多出现3次，所以2位bit即可表示。
 * 
 * 优点：占用空间少，同样可以用来找count为任意值的数字。
 * 		若需要查找操作，时间复杂度O(1)。
 * 		另外，对题目而言此方法只需在建立过程中，若判断count==3，即为结果。
 * 缺点：需要使用额外空间。
 * 复杂度：空间复杂度O(n)，时间复杂度O(n)。
 */

/**
 * 法三：使用本数组自身存储（元素*N），根据元素哈希值计算应该存储的位置。
 * 若发生冲突则往后顺延（到末尾则移至开头），之后遍历找到count为3的数字。
 * 
 * 优点：不适用额外空间，可以用来找count为任意值的数字。
 * 缺点：时间复杂度虽然同为O(n)，但遍历次数更多。
 * 复杂度：空间复杂度O(1)，时间复杂度为O(n)。
 * 问题：如何判断存储位置的值与本身相同（冲突情况下）？
 */

但是，法三中的问题一直没想到如何解决。实际上就是：如何把数组中的数字映射到一个确定的位置（不发生冲突或发生冲突后依然可以辨认出原来的数字）。在这种方法中，如果是数组中数字为1~n，就很好解决，直接使用k-1作为数组下标即可。但是，如果数字的范围不确定，就无法将数字与位置一一映射。此时，不管数字重不重复，我们好像都无法解决数据映射位置冲突的情况。【存疑：无法解决吗？】

看了“待字闺中”微信号的解答，发现还遗漏了好多思路。最简单的如排序后统计，就没有往这方面去想。。

/**
 * 法四：快速排序，之后寻找连续为3的数字。
 * 复杂度：时间复杂度O(nlog(n))。
 */

另外，还有的同学思路是：

/**
 * 法五：取得A中所有元素的乘积p（假设p没有溢出），遍历数组查看p%(A<sub>i</sub>^3)
 * 是否为0；若为0，则遍历数组查看A<sub>i</sub>出现次数是否为3.
 * 复杂度：时间复杂度O(n^2)。
 */

陈立人老师在微信号里只是给了这几个思路，并没有给出解答，而是留了一个思考题目：上面这个题目能否在时间复杂度O(n)，空间复杂度O(1)的条件下完成？如果不能怎么说明？

我想了下，能够想到的时间复杂度O(n)，空间复杂度O(1)的方法只有之前提到的法三，但是如何映射的问题还是没有解决。【存疑：如何解决，或者有其他的方法吗？】

查看了微博上的留言，有人的方法如下：

宝宝的贝贝先生：继续开一个大小32的数组，求二进制数位和，模3得到出现1,2次的数位和，模2得到出现1,3次的数位和，所有的数位和减去模2的得到出现2次的数位和，再类似折腾下就出来了… (9月11日 14:16)

但有人认为行不通：

Li-D-SM：回复@宝宝的贝贝先生:感觉行不通，只看最低位，1的个数若为5.(1,1,1,3,5)(1,1,3,3,5,6,6,6).对于同样的5而言，1,6在最低位的数显然是不同的，无法得到出现三次的数字最低位是1还是0 (9月12日 13:22)

唔，我还没看懂。【存疑】

下面对在数组中，统计数字出现次数的题目进行总结：

万金油解法HashMap统计；
对数字进行统计若重复不多（如1、2次等）时，可以考虑bitmap； 3. 数组排序后统计；
所有元素乘积对某元素的n次方取余，之后再判断是否确定（适用于元素为质数的情况，就无需再次确定，时间复杂度可以由O(n^2)变为O(n)）；
使用本数组*N存储，哈希寻找存储位置？【存疑：问题未解决】 6. 二进制数位和方法？【存疑】

另外，若是要我来选的话，2位的bitmap方法不错，虽然需要额外的空间，但实际中比HashMap需要的空间最优1/32（HashMap中需要存储key和value，至少两个int），实际表现应该不错。而且可扩展性强，可以持续添加新的数字（排序就不行，每次需要重排）；查找操作快，对于其他数字的查找count操作的时间复杂度为O(1)（排序的查找操作为O(n))。另外，bitmap方法对题目而言无需完全建立，只需在建立过程中，若判断count==3，即为结果。整体表现还是不错的。

Ex0907：找数字

这一道其实是上一道题的前一道题目，题目如下：

数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。

同样的，我们可以看到，前面所提到的：万金油HashMap、2位Bitmap、排序后统计、所有元素相乘后相除再判断的方法都可以实现，但是都不够快。题目中要找到最快的方法。

一般程序执行，最快的就是位操作了。我们想到了异或。但是会发现，如果其他数字都出现了2次（或偶数次），而x出现1次（或奇数次），用异或可以。但题目中其他数字也是出现了奇数次，因此，异或就失效了。

那是不是就不能应用位操作了呢？不是的。

题目中，如果数组中的元素都是三个三个出现的，那么从二进制表示的角度，每个位上的1加起来，应该可以整除3。

如果某个特定位上的1加起来，不可以被3整除，说明对应x的那位是1。若可以被3整除，则为0。

根据这一思想，我们可以开辟一个大小为32的int数组B，其中在int B_i中，保存A中所有元素的二进制表示中第i位的和。这样，最后，我们把得到的数组都对3取余，得到的就是x的各个位，转化为十进制即可。

【思考】其实我们想一下，使用异或来进行位运算的时候，也是相当于把对应位出现的次数进行保存了。不过异或是通过把两个1消去为0来保存，使得只出现1次的1显露出来。因此，异或的限制在于只能保存/消去偶数个位的值。而使用int数组来保存对应位的出现次数，相当于对此进行了扩展，通过使用额外空间来获得更多信息的保存结果。

我们可以看到，这个思路很巧妙。通过开辟一个长度32的数组，即可把数组中对应位上出现1的次数进行统计了。占用空间不大，但是效率很高。另外，这个方法限制也少。

这个方法不限制特殊数字x出现的次数是否为1，也就是说，加入其它数字都出现k次，那么只要x出现次数不为k即可（注意：若x出现次数大于k，也不影响最终对位的判断，只是最终某一位的统计结果取余后与x出现次数相差k的整数倍）。
如果在数组中，只有一个数字是特殊的，那么一定要利用其它数字的特性，可以通过异或、对应位相加（使用int保存每个位相加的结果）等方法，来把这个一个特性区别出来。

不过，最后，陈利人老师还给留了一个思考题：这里申请了一个数组的空间，如果这个是不被允许的呢？【存疑：该如何呢？】

Ex0828

给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。能够在O(n)的时间复杂度，O(1)的空间复杂度要求下完成么？

有了前面题目的基础，我想这道解决起来就不在话下了。由于有了新的条件，数组元素为1到n的数字，这个条件很强，把数字约束到1~n的范围内了。我们先把各个可能的解法列出来，之后分析其空间和时间复杂度。如下：

法一：万金油HashMap方法继续一马当先。不过空间复杂度O(n)，时间复杂度O(n)；

法二：由于没有说数字出现多少次，因此使用bitmap不太合适。不过我们可以变通一下，使用int来代替bitmap，毕竟，bitmap的思想其实相当于使用bit位来代替int，通过1bit位来保存“是”、“否”的信息。本来是为了节省空间的，但由于无法确定到底几次，而题目又要求统计哪些数字出现多少次，因此，通过使用int数组来统计对应n的出现次数。空间复杂度O(n)，建立时的时间复杂度为O(n)，查找时的时间复杂度O(1)；

法三：排序后统计，这个不多说。快排时间复杂度永远的O(nlog(n))；

法四：来到我们在最开始想到的使用数组本身来存储。由于这个题目中的数字为1~n，正好可以一一映射到数组的各个位置上，不会发生冲突。正是使用该方法的极好条件。由于数组中，下表是0~n-1的，我们可以将值为k的数字，映射到k-1的下表位置上。算法步骤如下：

遍历数组，每个元素 * = N(N为数组长度)；
遍历数组，根据元素的原值（k=元素现值/N），在k-1的位置上+1；
遍历数组，每个元素 %= N，即为改位置所对应元素的出现次数。

这样，通过遍历三次数组，就可以实现统计各元素的出现次数了（如果数组需要还原，还需再遍历一次）。空间复杂度O(1)，时间复杂度O(n)。

其他的方法，例如所有元素相乘、异或(位运算)等，由于数字出现并不如之前一样有规律，因此无法使用。

我们可以看到，目前来看，只有使用数组本身存储的方法可以达到O(1)的空间复杂度，同时满足O(n)的时间复杂度。其他方法一般都需要开辟额外的O(n)的空间。除此之外最好的方法应该是int数组，只需32 * n的空间，遍历一次即可，并且之后查找的时间复杂度都可以是O(1)。

最后，我们通过一道题目来对所有方法的特点、优点、使用要求、适用范围等方面做一个总结。

Ex0822

从1到n，n个数字，每个数字只出现一次。现在，随机拿走一个数字，请给出方法，找到这个数字。如果随机拿走两个数字呢？如果随机拿走k个数字呢？

好了，拿到这道题，我们继续来思考。我们先来只考虑第一个问题。题目给出的条件很强，数字是从1~n的数字，限制了数字的范围；每个数字只出现一次，限制了数字出现的次数；随即拿走了一个数字，说明只有一处是与其他不同、不符合规律的。我们可以利用这些特点来选择合适的解法。

法一：还是万金油HashMap，但它O(n)的空间复杂度和O(n)的时间复杂度使得一般这不是面试、笔试时想要的答案。注意：这只是不适用于面试、笔试，因此这种情况一般想考如何使算法最优、使复杂度降到最小。但是，HashMap的优势在于它的通用性，我们可以看到，之前所有的数组问题都可以使用HashMap求解，因此，在工程上HashMap应该更通用。

法二：排序。这种方法类似于HashMap，也属于万金油解法。但它O(nlog(n))的时间复杂度一般也不是最优解答，所以大部分只能作为备选。

法三：bitmap或int数组。这个很适合解答题目。由于bitmap或int数组中，天然包括了数字的顺序属性（使用下标），因此，均可以使用一次遍历建立后，便使用O(1)的时间复杂度来查找对应数字的出现次数等信息。bitmap和int数组二者的区别只在于由于占用的空间大小不同，所以存储的消息容量不同。

法四：使用数组本身存储信息。这种方法可以存储数字出现次数等信息，所需要解决的只是数字和对应位置的映射问题。由于需要各个数字出现的详细信息，因此映射需要为一一映射。（现在还没遇到不需要一一映射的题目）。此方法的优点在于O(1)的空间复杂度，这常常是考察的重点。在本题目中，已经满足一一映射的条件，因此可以使用这种方法解答。算法步骤见上一题。

法五：所有元素相乘/相加法。由于只有一个元素被拿走，因此，我们只需要先算出n的阶乘，再除以现存所有数字的乘积，即可得到拿走的数字。该方法也可以。

法六：位运算。位运算法如果可以使用的话，应该是计算最快的方法。当然，该方法对条件要求也较苛刻，一般需要所有元素中只有一个是不符合规律的（如Ex0907和此题），才有可能使用这种方法。在本题目中，对1~n所有元素进行与运算，在对取走一个元素后剩下的元素进行与运算，二者异或，即可得拿走的数字。

其他的暂时还没有想到，等遇到了再来补充。

下面我们继续将此题进行推广。题目中要求，如果随机拿走2个数字、k个数字的情况又该如何？

一般情况下，在题目中，i = 1,2,3,…,k,…n，都是需要考虑的情况。后面是前面的一般形式，前面是后面的特殊情况。

在本题中，k=1的特殊情况已经讨论完毕。对于拿走2个、k个数字的情况来说：

法一、法二是万金油毫无压力；

法三、法四也是包含了所有数字的统计信息，属于通用解法；

法五、法六来说，看起来就无法确定到底是哪个数字了。不过，陈立人老师给出的答案中，对这两种方法进行了推广，使得其可以处理k个数字被拿走的情况。

法五的推广：原来在法五中，我们只对原始数据集和新数据集计算了求和或阶乘，依次求得被拿走的一个数字。但在被拿走k个数字之时，我们还可以根据原始数据集得到更多的条件，来求解丢失的数字。考虑如下：

square_sum_more = n个数的平方和
square_sum_less = n-2个数的平方和

我们可以据此构造一个新的等式，再加上原来的差值，则有：

square_sum_more - square_sum_less = a^2 + b^2
sum_more - sum_less = a + b

这样就化为求解二元方程了。如果是三个数字，可以再构造立方方程即可。以此类推，当消失k个数字的时候，算法的时间复杂度为O(kn)。

这样，就相当于对法五进行了扩展，使得可以处理多个元素丢失的情况。

法六的推广：

另外，微博上的一位同学@曹鹏博士，给出了一个O(nlogn)的解法，也是非常巧妙的，具体是采用分治法：知道1-n最低bit有多少个为0，多少个为1。然后统计一下，给出的数最低bit有多少个为0，多少个为1；然后就知道从最低bit为0的那部分取走了k0个数，从最低bit为1那部分取走了k1个数。其中，k0 + k1 = k。然后把那些数按照最低bit为0，为1分开。问题变为两个子问题k0,k1，然后再考虑次低bit。很不错的解法。

因此，法一到法六，都可以解决或通过推广解决k个数字的问题。我个人比较偏向法三、法四，占用额外空间不大，时间复杂度有效降低，算法实现也简单。

数组类题目之统计数字出现次数总结

我们可以看到，对数组中的数字进行统计的时候，我们需要对统计得到的信息进行存储。把这些信息存储在哪？这就涉及到空间复杂度的问题。

法一中，HashMap为了保存一一对应关系，使用了较多的额外空间O(n)作为代价，换来的是全部的统计信息，结果是万金油解法，虽然占了空间，但是包打天下。

法二中，排序也是万金油打法。对于所有数字进行重排，则所有的统计信息都可以通过顺序读取得到。重拍是通过使用较多的时间代价，来换取全部统计信息的排序，因此它在时间复杂度上有劣势，O(nlog(n))一般都不太适用于这类问题。

法三中，bitmap或int数组比较巧妙的利用了数组中天然包含的下表信息来代替位置信息，因此，对于可以将数组一一映射的情况下，可以使用较少的空间来保存统计信息。他虽然是O(n)的空间复杂度，但是比HashMap需要的空间小很多，尤其是bitmap，工程中可以降低10倍以上，实际上占用不了太多的空间，而且，他还有一个优势就是，在构建完毕之后，查找所有元素的时间复杂度都是O(1)，这一点很不错。

法四中，与法三类似，使用数组本身存储信息也需要建立数组中数字与数组中所需存储位置之间的一一映射。只不过，法三中，是将统计信息保存在额外的空间中，而本方法中，则是保存在元素 * N之后的余数中，通过再对元素取模来将此数取出。（在此法中，还有一个技巧，就是不是初始化时所有元素乘N，之后通过加1来保存统计信息；而是通过每次加N来保存统计信息，这样计算结果的时候，直接除N即为次数信息，对N取模即为原元素值）

法五中，所有元素相乘/相加法。他的适用范围比较窄，一般只用来解决有规律的数中，有一个数不符合规律的情况。因为如果有两个或以上的数不规律的话，可以通过推广形式，得到平方、立方等的差值，从而得到多个n元方程，转化为方程求解问题。

法六中，由于在计算机中，位运算速度最快，占用空间也小，因此这也是常考的方法。位运算常用的是异或运算，如本题所示。另外，如Ex0927中，通过建立一个长度为32的int数组，来保存所有数字在各个位上出现的次数，通过对k取模来找到出现特殊次数的值，也是一种很巧妙的应用方法。在本题中，@曹鹏博士的解答也是一个变种，通过统计bit位上缺失的数字来进行分治法，也额外开辟了空间来储存这些信息。

好了，分析完各个方法的优缺点，下面我们来个终极总结篇。

终极总结

思考：只关注数组类中，统计数字出现次数的情况下，那么可以从哪些角度出题呢？如果需要在数组中保存信息（如统计信息）的话，有哪些途径可以保存信息呢？又有哪些途径不保存信息但是可以获取信息呢？最后一个问题，如果让你出题，你该怎么出？

一般而言，出的题目都是寻找出现特定次数的数字、缺失的数字。给出的条件包括：其他数字是规律出现的（如出现3次等）、其他数字出现无规律、数字范围被限定（如1~n）、数字无限制等条件；给出的要求包括：空间复杂度为O(1)、时间复杂度尽量小的比较多。

解题的思路是很对应的。HashMap和排序后统计是万金油解法，但一般不是考察的目的。如果题目数字很规律（如1~n等），可以考虑位运算（异或、相与等），或者使用数组本身存储，或者使用所有元素相乘/相加/平方等转化为n元方程求解问题；如果数字出现次数是有限的，可以考虑使用bitmap或int数组存储；如果数字出现次数是规律的（如出现3次等），可以考虑使用数组存储原数字的bit位信息，来统计得到缺失或多于的数字的bit位。

在解答中，需要保存信息的话，出了开辟新的空间（O(n)的空间复杂度），还可以在本数组中保存，这样，有一部分信息数字信息可以通过映射保存在数组的下表中，替代了HashMap中的key值的作用，节省了空间。bit位的异或或相与也可以不保存而获取信息，不过只能有1bit的信息，需要考虑如何利用。

最后一个问题，唔，貌似我还没到出题的水平，或者说，已经跳不出被这样思路禁锢的区域了。如果有新题目，我再来补充吧。

思维导图：