題目描述
????數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半患蹂，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次蹋盆，超過數(shù)組長度的一半，因此輸出2硝全。
解題思路
????數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半栖雾，也就是說他出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)還要多。因此我們可以考慮在遍歷數(shù)組的時候保存兩個值：一個是數(shù)組中的一個數(shù)字伟众，另一個是次數(shù)析藕。當我們遍歷到下一個數(shù)字的時候，如果下一個數(shù)字和我們之前保存的數(shù)字相同凳厢，則次數(shù)加1账胧；如果不同則次數(shù)減1竞慢。如果次數(shù)為0，那么我們需要保存下一個數(shù)字并把次數(shù)置為1.由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字的次數(shù)和還要多治泥，那么要找數(shù)字肯定是最后一次把次數(shù)置為1時所對應的數(shù)字筹煮。
Java代碼實現(xiàn)
/**
* 尋找出數(shù)組中出現(xiàn)次數(shù)超過一般的數(shù)字
* @author Administrator
*
*/
public class Exe40_FindNumMoreThanHalf {
public static void main(String[] args) {
int[] datas={1,2,3,2,2,2,5,4,2};
System.out.println(solution(datas));
}
public static int solution(int[] datas) {
if(datas==null||datas.length==0){
return 0;
}else {
int currentData=datas[0];
int currentNum=1;
for(int i=1;i<datas.length;i++){
if(currentNum==0){
currentData=datas[i];
currentNum=1;
}else if(currentData==datas[i]){
currentNum++;
}else {
currentNum--;
}
}
if(isResultValid(currentData,datas)){
return currentData;
}else {
return 0;
}
}
}
private static boolean isResultValid(int result,int[] datas) {
int num=0;
for (int i : datas) {
if(result==i) num++;
}
if(num>datas.length/2)
return true;
else
return false;
}
}
