1
#yyds干货盘点# 面试必刷TOP101：数组中出现次数超过一半的数字
source link: https://blog.51cto.com/u_15488507/5680769
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：数组中出现次数超过一半的数字
精选 原创1.简述：
描述
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
数据范围：，数组中元素的值
要求：空间复杂度：，时间复杂度
输入描述：
保证数组输入非空，且保证有解
示例1
[1,2,3,2,2,2,5,4,2]
示例2
[3,3,3,3,2,2,2]
示例3
2.代码实现：
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)return 0;
int preValue = array[0];//用来记录上一次的记录
int count = 1;//preValue出现的次数（相减之后）
for(int i = 1; i < array.length; i++){
if(array[i] == preValue)
count++;
else{
count--;
if(count == 0){
preValue = array[i];
count = 1;
}
}
}
int num = 0;//需要判断是否真的是大于1半数，这一步骤是非常有必要的，因为我们的上一次遍历只是保证如果存在超过一半的数就是preValue，但不代表preValue一定会超过一半
for(int i=0; i < array.length; i++)
if(array[i] == preValue)
num++;
return (num > array.length/2)?preValue:0;
}
}
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)return 0;
int preValue = array[0];//用来记录上一次的记录
int count = 1;//preValue出现的次数（相减之后）
for(int i = 1; i < array.length; i++){
if(array[i] == preValue)
count++;
else{
count--;
if(count == 0){
preValue = array[i];
count = 1;
}
}
}
int num = 0;//需要判断是否真的是大于1半数，这一步骤是非常有必要的，因为我们的上一次遍历只是保证如果存在超过一半的数就是preValue，但不代表preValue一定会超过一半
for(int i=0; i < array.length; i++)
if(array[i] == preValue)
num++;
return (num > array.length/2)?preValue:0;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK