多数投票算法（MajorityVoteAlgorithm）
假设有⼀个数组，其中含有N个⾮负元素，求其中是否存在⼀个元素其元素个数⼤于等于N/2。
分析：看到这个问题最先想到的是暴⼒算法，将数组在O(NlogN)的时间内进⾏排序，然后扫描⼀次数组就知道是否存在满⾜条件的元素了。
算法实现：
int Majority_Vote_Sort(const int* a, const int n)
{
sort(a,n);
int count=0;
int max = 0;
int now = a[0];
int res = a[0];
怎么查四级成绩for(int i=1; i<n; i++)
{
if(a[i] == now)
kirkland
{
count++;
}
el界面英文
{
if(count > max)dea
{
max = count;
res = now;
}
now = a[i];
count = 0;
}
}
return max;
//return res;
}
上述算法可以在O(logN)的时间内找到满⾜条件的元素，但是仔细观察发现，算法中对数组的排序似乎是多余的，为此可以在算法排序处进⾏⼀定的改进便可以得到更加快速的算法。
学过hash表的同学看到这个问题通常容易想到使⽤⼀个定义⼀个数组count，其中数组的⾓标为原来数组的元素值，count数组的元素值代表了这个⾓标元素出现的次数，由此可以在扫⾯⼀遍数组的情况下获得原数组中各个元素的个数，从⽽解决此题。也可以利⽤hash表来替代count数组，这样做的话算法的鲁棒性会更好。
算法实现
int Majority_Vote(const int* a, const int n)
{
int* res = new int[n];
for(int i=0; i<n; i++)
res[i] = 0;
for(int i=0; i<n; i++)
bbc中国新年res[a[i]]++;
luka rocco magnotta
int max = res[0];
for(int i=1; i<n; i++)
{
if(max < res[i])
max = res[i];
}
delete[] res;
return max;
}
上述算法在时间复杂度上做到了最优，但是却花费了额外的空间复杂度，为此，查阅⽂献的时候发现了⼀个很神奇的⽅法 ，此⽅法只需在常数空间复杂度上就可以实现上述算法的功能。
神奇算法的思路：（存在⼀个计数器count和⼀个临时存储当前元素的变量now）
1. 如果count==0，则将now的值设置为数组的当前元素，将count赋值为1；
2. 反之，如果now和现在数组元素值相同，则count++，反之count--；
3. 重复上述两步，直到扫描完数组。
4. count赋值为0，再次从头扫描数组，如果素组元素值与now的值相同则count++，直到扫描完数组为⽌。
5. 如果此时count的值⼤于等于n/2，则返回now的值，反之则返回-1；
算法实现
6级int Majority_Vote_update(const int* a, const int n)
{
struct item
{
int now;
int count;
};
item* t = new item;
t->count = 0;
for(int i=0; i<n; i++)
{
if(t->count == 0)
{
t->now = i;
t->count = 1;
}
el
{
if(t->now == a[i])
t->count++;
el
t->count--;
}
}
int res=0;
for(int i=0; i<n; i++)
{
if(t->now == a[i])
博士英语res++;
}
if(res >= n+1/2)
return res;
el
让杜雅尔丹return -1;
}
上述算法只需在常数的额外空间的条件下就可以在常数的时间内判断并找出符合条件的元素。
此⽂仅供参考，若要挖掘算法的理论基础，请点击
学过hash表的同学看到这个问题通常容易想到使⽤⼀个定义⼀个数组count，其中数组的⾓标为原来
数组的元素值，count数组的元素值代表了这个⾓标元素出现的次数，由此可以在扫⾯⼀遍数组的情况下获得原数组中各个元素的个数，从⽽解决此题。也可以利⽤hash表来替代count数组，这样做的话算法的鲁棒性会更好。
rt算法实现
