如何做网站流量买卖/潍坊网站建设

解题思路:

摩尔投票法
若存在该数, 则一定有所有数字的票数和 > 0
若数组的前a个数字的票数和 = 0, 则数组剩余( n - a )个数字的票数和一定仍 > 0, 即后( n - a )个数字符合题目要求的数仍为x

1.从该数组[1, 2, 3, 2, 2, 2, 5, 4, 2]的第一个数1开始, 假设1是题中要找出的数字x, 那么票数votes为+1
2.数组第二个数字2不是x, 那么票数votes为-1
3.该数组的前两项票数和为0
4.接下来假设数组的第三个数3是题中要找出的数字x, 那么票数votes为-1
5.数组第四个数字2是x, 那么票数votes为+1
6.该数组的第三项和第四项票数和为0
…
依次类推
就可得出x

tips: 此题需要注意的一个点在于题中并未说明一定存在该数, 所以最后要判断num是否符合题目要求

public class Solution {public int MoreThanHalfNum_Solution(int [] array) {int votes = 0, x = 0, count = 0;for(int num : array){if(votes == 0){x = num;}votes += num == x ? 1 : -1;}for(int num : array){if(num == x){count++;}}return count > array.length / 2 ? x : 0;}
}