题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
一个数字出现的次数超过数组长度的一半<=>这个数字出现的次数可以抵消所有其它数字出现的次数首先对elem=a[0]进行计数cnt=1, 当后面a[i]为elem时，就cnt++，否则cnt--，当cnt减为0时，从elem=a[i]重复前面的动作。这样最终所求数字只可能是elem或者不存在。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> vec) {
if (vec.empty())
{
return 0;
}
int cnt = 1;
int elem = vec[0];
for (int i = 1; i < vec.size(); ++i)
{
if (vec[i] == elem)
{
cnt++;
}
else
{
cnt--;
if (cnt == 0)
{
elem = vec[i];
cnt = 1;
}
}
}
cnt = 0;
for (int i = 0; i < vec.size(); ++i)
{
if (vec[i] == elem)
{
cnt++;
}
}
if (cnt > vec.size() / 2)
{
return elem;
}
return 0;
}
};
，大部分都转正了
海康威视公司氛围 407人发布