面试题39:数组中出现次数超过一半的数字
程序员文章站
2024-02-27 16:16:03
...
题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如,输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。
package jianzhi_offer;
public class P39_Solution {
/*
* 解题思路:遍历数组的时候保留连个值,一个是数组中的数字,另一个是次数。如果下一个数字和我们之前保留的数字相同,则次数加1;如果下一个数字和
* 之前保留的数字不同,则减1.如果次数为零,我们需要保存下一个数字,并把次数设为1.由于我们要找的数字比其他所有数字出现的次数之和还要多,
* 我们要找的数字肯定是最后一次把次数设为1时对应的数字。
*/
public boolean isCheckMoreHalf(int [] array, int result) {
int times = 0;
for(int i=0; i<array.length; i++) {
if(array[i] == result) {
times++;
}
}
if(times*2 > array.length)
return true;
return false;
}
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length <=0)
return 0;
if(array.length == 1)
return array[0];
int times = 1;
int result = array[0];
for(int i=1; i<array.length; i++) {
if(times == 0) {
result = array[i];
times = 1;
}else {
if(array[i] == result) {
times++;
}else {
times--;
}
}
}
if(!isCheckMoreHalf(array, result))
return 0;
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
上一篇: Linux软链接的创建、删除和更新
下一篇: Java创建表格实例详解 原创