题解 | #数组中出现次数超过一半的数字#

摩尔投票法：寻找超越一半的数字

• 假设arr[0]是超越一半的数，遍历集合：
  • 若遍历元素和arr[0]相同，则count + 1;
  • 若遍历元素和arr[0]不同，则count - 1;
• 如果计数为0，说明前面的数字被抵消，数量超越一般的数组在后面。

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int x = array[0], count = 0;
        for(int num : array){
            if(count == 0) x = num;
            count += num == x ? 1 : -1;
        }
        return x;
    }
}

排序取中：
若某数的数量超过一半，则有序数列的中点就是该数。

import java.util.*;
public class Solution {
     public int MoreThanHalfNum_Solution(int [] array) {
         Arrays.sort(array);
         return array[array.length / 2];
    }
}