数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
//方案一
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int len=array.length;
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
for(int i=0;i<len;i++){
if(!hash.containsKey(array[i]))
hash.put(array[i],1);
else
hash.put(array[i], hash.get(array[i]) + 1);
if(hash.get(array[i])*2>len)
return array[i];
}
return 0;
}
}
//方案二 网友称为分形叶的思想
import java.util.*;
public class Solution { public int MoreThanHalfNum_Solution(int [] array) {
int len=array.length;
int result = array[0];
int time=1;
for(int i=1;i<len;i++)
{
if(time==0){
time=1;
result=array[i];
}else
if(result==array[i])
time++;
else
time--;
}
int sum=0;
for(int i=0;i<len;i++)
if(array[i]==result)
sum++;
if(sum*2>len)
return result;
else
return 0;
}
}
//方案三:
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int len=array.length;
int mid=len/2;
int start=0;
int end=len-1;
int index = f(array,start,end);
while(index!=mid){
if(index>mid)
index=f(array,start,index-1);
else
index=f(array,index+1,end);
}
int result=array[mid];
int sum=0;
for(int i=0;i<len;i++)
if(result==array[i])
sum++;
return sum*2>len?result:0;
}
public int f(int input[],int begin,int end){
int low = begin;
int high = end;
int pivot = input[low];
while (low < high)
{
while (low < high&&pivot <= input[high])
high--;
input[low] = input[high];
while (low < high&&pivot >= input[low])
low++;
input[high] = input[low];
}
input[low] = pivot;
return low;
}
}
推荐方案二,方案其实很差,但是提供了一个球第k大数的思路