问题描述

数组中有一个数字出现次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。

由于数字2在数组中出现了5次，超过数组长度一半，因此输出2

问题分析

首先想到的是，可以维护一个数据结构用来存储每个数字对应的出现次数。没遇到一个新的数字就去找这个数字是否出现过，如果出现过就加1.这种思路最简单，但是时间复杂度是O(n^2)。

稍做优化，可以把数组排序，然后中位数一定是要找的数。这样的时间复杂度是O(nlogn)

还可以再试着优化，第一种方法之所以需要O(n^2)的时间复杂度是因为找一个数是否已经出现过，需要O（n）的时间复杂度，拿能不能用Hash呢。很不幸的是也不行，因为不知道数字的取值范围，无法构造hash函数。否则的话，也不用hash，直接基数排序就解决问题了。

似乎最快的算法就是排序的O（nlogn）了。如果还想优化，关键在于利用“出现次数超过一半”这个条件的数学性质。

理论基础

为了后面的解释，我们首先定义：
对于数组A，出现次数超过一半的数记为H(A)

还是以之前的数组A{1,2,3,2,2,2,5,4,2}为例,首先有H(A) = 2，我们观察一下这个2的特点：

如果把前两个数1和2去掉，剩下的数组A’是{3,2,2,2,5,4,2}，H(A’)依然为2！

更进一步，我们可以这么想，既然前两个数去掉之后不影响找出现次数超过数组长度的一半的数字，那么任意去掉相邻的两个数字也不影响呢。

也就是说对于任意数组A和A去掉两个相邻数字的子数组A’是否都有:H(A) = H(A')

很不幸，这个结论也不成立，因为如果在刚刚的数组A中去掉连续的两个2，就不对了。但是只要稍稍把结论修改一下就是成立的：
对于任意数组A，去掉A中任意两个相邻但不相等的数，得到数组A’,总有H(A) = H(A')

结论很好证明：设H(A) = p,去掉的两个数中最多有一个p，由于p原来出现的次数大于n/2，现在p-1自然一定大于(n-2)/2。所以H（A'）= p。

编程实现

有了刚刚的结论，再看这个数组就简单多了。只要把数组从头到尾遍历一遍，剔除相邻的不同的数就可以。比如数组中有一段是{1，2，3，4}，可以预见到，有可能是{2，3}先被比较，然后被剔除，接着是{1，4}变成相邻的，接着被剔除。

为了避免反复循环，在一个循环里解决问题，自然而然的想到了一个数据结构——“栈”。

只要对于数组中的每一个元素，如果栈为空或这个元素与栈顶元素相同，则这个元素入栈，否则栈顶元素出栈即可。这样一来，不相同的数即使不相邻，迟早也会一起出栈（可以把用来和栈顶做比较元素想象为先入栈再出栈）。

所以这样一来，代码会非常简洁优雅：

int findNumber(std::vector<int> v){
    std::stack<int> stack = std::stack<int>();
    for (int i = 0; i < v.size(); ++i) {
        if (stack.empty() || stack.top() == v[i]) {
            stack.push(v[i]);
        }
        else{
            stack.pop();
        }
    }
    return stack.top();
}

正确性证明

对于H(A)这个数来说，它想要出栈的唯一可能是遇到一个和它不同的数（之前说过，如果把H(A)和与它不同栈顶元素比较，可以理解为H(A)先进栈再出栈）。

而在数组A中，剩下所有的数出现次数的和一定小于H(A)出现的次数。所以最终的栈里一定只剩下若干个H(A)。

拓展1——判断是否存在这样的数

之前我们都是基于题干所说的，出现次数超过一半的数是存在的，这一前提进行分析。如果把题干改为：
判断出现次数超过一半的数是否存在，如果存在则找出这个数

这时候，我们依然用同样的方法先得到之前所说的栈。这个栈如果为空，则H(A)不存在（因为已经证明H(A)存在的话栈中的数都等于H(A)）。如果不为空，也只有可能有一种数字，不妨记为x。

x不一定是要找的H(A)，因为H(A)不一定存在。我们只能说如果H(A)存在的话，x = H(A)。所以只要重新遍历数组，看看x的出现次数是否超过n/2即可。

拓展2——不少于一半

看到一个非常有意思的问题，即把题干改为找到出现次数不少于一半的数。其实非常简单的方法是判断数组的第一个元素是否满足要求。如果不满足的话，剩下的n-1个数构成数组A’，则H(A’)就是要找的数。相当于划归为了之前已经解决的问题。