题意: 数组中有一个数字出现的次数超过了数组长度的一半, 找出这个数字.
分析与解法
一个数组中有很多数, 现在我们要找出其中那个出现次数超过总数一半的数字, 怎么找呢? 大凡当我们碰到某一个杂乱无序的东西时, 我们人的内心本质期望是希望把它梳理成有序的. 所以, 我们得分两种情况来讨论, 无序和有序.
解法一
如果数组无序, 那么我们是不是可以先把数组中所有这些数字先进行排序(至于排序方法可选取最常用的快速排序). 排完序后, 直接遍历, 在遍历整个数组的同时统计每个数字的出现次数, 然后把那个出现次数超过一半的数字直接输出, 题目便解答完成了. 总的时间复杂度为 \(O(nlogn + n)\).
但如果是有序的数组呢, 或者经过排序把无序的数组变成有序后的数组呢? 是否在排完序 \(O(nlogn)\)后, 还需要再遍历一次整个数组?
我们知道, 既然是数组的话, 那么我们可以根据数组索引支持直接定向到某一个数. 我们发现, 一个数字在数组中的出现次数超过了一半, 那么在已排好序的数组索引的 \(N/2\)处(从零开始编号), 就一定是这个数字. 自此, 我们只需要对整个数组排完序之后, 然后直接输出数组中的第 N/2 处的数字即可, 这个数字即是整个数组中出现次数超过一半的数字, 总的时间复杂度由于少了最后一次整个数组的遍历, 缩小到 \(O(n*logn)\).
然时间复杂度并无本质性的改变, 我们需要找到一种更为有效的思路或方法.
解法二
既要缩小总的时间复杂度, 那么可以用查找时间复杂度为 O(1)的 hash 表, 即以空间换时间. 哈希表的键值 (Key) 为数组中的数字, 值 (Value) 为该数字对应的次数. 然后直接遍历整个 hash 表, 找出每一个数字在对应的位置处出现的次数, 输出那个出现次数超过一半的数字即可.
解法三
Hash 表需要 O(n)的空间开销, 且要设计 hash 函数, 还有没有更好的办法呢? 我们可以试着这么考虑, 如果每次删除两个不同的数 (不管是不是我们要查找的那个出现次数超过一半的数字), 那么, 在剩下的数中, 我们要查找的数(出现次数超过一半) 出现的次数仍然超过总数的一半. 通过不断重复这个过程, 不断排除掉其它的数, 最终找到那个出现次数超过一半的数字. 这个方法, 免去了排序, 也避免了空间 O(n)的开销, 总得说来, 时间复杂度只有 O(n), 空间复杂度为 O(1), 貌似不失为最佳方法.
举个简单的例子, 如数组 a[5] = {0, 1, 2, 1, 1};
很显然, 若我们要找出数组 a 中出现次数超过一半的数字, 这个数字便是 1, 若根据上述思路 4 所述的方法来查找, 我们应该怎么做呢? 通过一次性遍历整个数组, 然后每次删除不相同的两个数字, 过程如下简单表示:
0 1 2 1 1 =>2 1 1=>1
最终 1 即为所找.
此外, 对于序列{5, 5, 5, 5, 1}, 每次分别从数组两端尝试各删除一个数(左边删除 5, 右边删除 1, 两个数不相同), 之后剩余{5, 5, 5}, 这时无法找到两个不同的数进行删除, 说明剩余元素全部相同, 返回 5 作为结果即可.
解法四
更进一步, 考虑到这个问题本身的特殊性, 我们可以在遍历数组的时候保存两个值: 一个 candidate, 用来保存数组中遍历到的某个数字; 一个 nTimes, 表示当前数字的出现次数, 其中, nTimes 初始化为 1. 当我们遍历到数组中下一个数字的时候:
如果下一个数字与之前 candidate 保存的数字相同, 则 nTimes 加 1;
如果下一个数字与之前 candidate 保存的数字不同, 则 nTimes 减 1;
每当出现次数 nTimes 变为 0 后, 用 candidate 保存下一个数字, 并把 nTimes 重新设为 1. 直到遍历完数组中的所有数字为止.
举个例子, 假定数组为{0, 1, 2, 1, 1}, 按照上述思路执行的步骤如下:
1. 开始时, candidate 保存数字 0,nTimes 初始化为 1;
2. 然后遍历到数字 1, 与数字 0 不同, 则 nTimes 减 1 变为 0;
3. 因为 nTimes 变为了 0, 故 candidate 保存下一个遍历到的数字 2, 且 nTimes 被重新设为 1;
4. 继续遍历到第 4 个数字 1, 与之前 candidate 保存的数字 2 不同, 故 nTimes 减 1 变为 0;
5. 因 nTimes 再次被变为了 0, 故我们让 candidate 保存下一个遍历到的数字 1, 且 nTimes 被重新设为 1. 最后返回的就是最后一次把 nTimes 设为 1 的数字 1.
思路清楚了, 完整的代码如下:
- //a 代表数组, length 代表数组长度
- int FindOneNumber(int* a, int length)
- {
- int candidate = a[0];
- int nTimes = 1;
- for (int i = 1; i <length; i++)
- {
- if (nTimes == 0)
- {
- candidate = a[i];
- nTimes = 1;
- }
- else
- {
- if (candidate == a[i])
- nTimes++;
- else
- nTimes--;
- }
- }
- return candidate;
- }
即针对数组{0, 1, 2, 1, 1}, 套用上述程序可得:
- i=0,candidate=0,nTimes=1;
- i=1,a[1] != candidate,nTimes--,=0;
- i=2,candidate=2,nTimes=1;
- i=3,a[3] != candidate,nTimes--,=0;
- i=4,candidate=1,nTimes=1;
如果是 0,1,2,1,1,1 的话, 那么 i=5,a[5] == candidate,nTimes++,=2;......
解法五
再进一步, 再次考虑这个问题本身的特殊性, 可以采用概率方法, 每次取两个数出来比较, 直到发现两个相同的数.(解法五的发散思维来自 Rogn dalao)
- #include<cstdio>
- #include<cstdlib>
- int main()
- {
- int a[] = {1, 2, 3, 4, 5, 6, 6, 6, 6, 6};
- int n = 8;
- int i = rand() % n;
- int j = rand() % n;
- while(a[i] != a[j])
- {
- i = rand() % n;
- j = rand() % n;
- }
- printf("%d\n", a[i]);
- }
复杂度:
任意两个数不同的概率
p 约等于 3/4,p^10= 0.056, 也就是说 10 次还没出结果的概率为 0.056, 已经比较小了.
有趣的是, n 越大, 该概率越小.
举一反三
题意: 找出出现次数刚好是一半的数字
分析: 我们知道: 有 N 个数, 其中有一个数出现超过一半, 要求在线性时间求出这个数. 那么, 我的问题是, 加强版水王: 有 N 个数, 其中有一个数刚好出现一半次数, 要求在线性时间内求出这个数.
因为, 很明显, 如果是刚好出现一半的话, 如此例: 0,1,2,1 :
遍历到 0 时, candidate 为 0,times 为 1
遍历到 1 时, 与 candidate 不同, times 减为 0
遍历到 2 时, times 为 0, 则 candidate 更新为 2,times 加 1
遍历到 1 时, 与 candidate 不同, 则 times 减为 0; 我们需要返回所保存 candidate(数字 2)的下一个数字, 即数字 1.
来源: https://www.cnblogs.com/RioTian/p/13321400.html