Majority Element
数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。
分析与解法
一个数组中有很多数,现在我们要找出其中那个出现次数超过总数一半的数字,怎么找呢?大凡当我们碰到某一个杂乱无序的东西时,我们人的内心本质期望是希望把它梳理成有序的。所以,我们得分两种情况来讨论,无序和有序。
解法一
如果 无序 ,那么我们是不是可以先把数组中所有这些数字 先进行排序 (至于排序方法可选取最常用的快速排序)。排完序后,直接遍历,在遍历整个数组的同时统计每个数字的出现次数,然后把那个出现次数超过一半的数字直接输出,题目便解答完成了。总的时间复杂度为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}
,还能运用上述思路么?很明显不能,咱们得另寻良策。
解法四
更进一步,考虑到这个问题本身的特殊性,我们可以在遍历数组的时候保存两个值:一个candidate
,用来保存数组中遍历到的某个数字;一个nTimes
,表示当前数字的出现次数,其中,nTimes
初始化为1
。当我们遍历到数组中下一个数字的时候:
- 如果下一个数字与之前candidate保存的数字相同,则nTimes加1;
- 如果下一个数字与之前candidate保存的数字不同,则nTimes减1;
- 每当出现次数nTimes变为0后,用candidate保存下一个数字,并把nTimes重新设为1。 直到遍历完数组中的所有数字为止。
举个例子,假定数组为{0, 1, 2, 1, 1}
,按照上述思路执行的步骤如下:
- 开始时,
candidate
保存数字0
,nTimes
初始化为1
; - 然后遍历到数字
1
,与数字0
不同,则nTimes
减1
变为0
; - 因为
nTimes
变为了0
,故candidate
保存下一个遍历到的数字2
,且nTimes
被重新设为1
; - 继续遍历到第
4
个数字1
,与之前candidate
保存的数字2
不同,故nTimes
减1
变为0
; - 因
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
;......
public class Solution {
public int majorityElement_1(int[] num) {
int n = num.length;
if (n == 0) return 0;
if (n == 1) return num[0];
int res = num[0], cnt = 1;
for (int i = 1; i < n; ++i) {
if (cnt == 0) {
res = num[i];
++cnt;
continue;
}
if (res == num[i]) ++cnt;
else --cnt;
}
return res;
}
public int majorityElement_2(int[] num) {
int n = num.length;
if (n == 0) return 0;
if (n == 1) return num[0];
int res = 0;
for (int i = 0; i < 32; ++i) {
int one = 0, zero = 0;
for (int j = 0; j < n; ++j) {
if (((num[j]>>i) & 1) == 1) ++one;
else ++zero;
}
if (one > zero) res = res | (1<<i);
}
return res;
}
}
举一反三
加强版水王:找出出现次数刚好是一半的数字
分析:我们知道,水王问题:有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
。