# 3 代码实现

## 解法一：

``````public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array==null){
return 0;
}
int mid = array.length/2;
int start = 0;
int end = array.length-1;
int pivot = partition(array,start,end);

while(pivot!=mid){
if(pivot<mid){
start = pivot+1;
pivot = partition(array,start,end);
}else{
end = pivot-1;
pivot = partition(array,start,end);
}
}

int count = 0;
for(int i=0;i<array.length;i++){
if(array[pivot]==array[i]){
count++;
}
}

return count>mid?array[pivot]:0;
}

private int partition(int[] array,int start,int end){
int pivot = array[start];
while(start<end){
while(start<end && array[end]>=pivot){
end--;
}
array[start] = array[end];
while(start<end && array[start]<=pivot){
start++;
}
array[end] = array[start];
}
array[start] = pivot;
return start;
}
}
``````

## 解法二：

``````public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array==null){
return 0;
}

int index = 0;
int count = 1;
for(int i=1;i<array.length;i++){
if(count==0){
index = i;
count = 1;
}
if(array[index]==array[i]){
count++;
}
else{
count--;
}
}

int times = 0;
for(int i=0;i<array.length;i++){
if(array[index]==array[i]){
times++;
}
}

return times>array.length/2?array[index]:0;
}
}
``````

comments powered by Disqus