day31(4.12)

1. 数组中出现次数超过一半的数字

• 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
• 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 ``` 示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

限制：

1 <= 数组长度 <= 50000

<a name="I5ge4"></a>
### 思路:
- 首先筛选出不重复的数
   - 使用Set，将所有数遍历存入Set，然后通过toArray()得到一个不重复的数组
- 循环遍历获取不重复的数，将每一个数与原数组中的数进行对比，如果相同那么计数器+1；
- 判断结果，如果计数器数值>数组长度/2，则该数就是目标数。
```java
class Solution {
    public int majorityElement(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i : nums){
            set.add(i);
        }
        int length = nums.length;
        int size = set.size();
        Integer[] arr = set.toArray(new Integer[0]);
        int count;
        for(int i=0;i<size;i++){
            count = 0;
            int n = arr[i];
            for(int j=0;j<length;j++){
                if(nums[j]==n){
                    count++;
                }
            }
            if(count>length/2){
                return n;
            }
        }
        return -1;
    }
}

优质的解法：摩尔投票（找到数组中超过半数的数）

• 因为数字个数需要大于数组长度的一半，那么就可以遍历，把第一个数当成目标数，如果第二个数与之相同，那么投票器+1，如果不同投票器-1；当投票器为0时，重新选择一个数进行投票。直到最后一个显示投票器数值>1对应的数就是目标数。

  class Solution {
    public int majorityElement(int[] nums) {
        int votes = 0,x=0;
        for(int i=0;i<nums.length;i++){
            if(votes==0) x=nums[i];
            votes += x==nums[i]?1:-1;
        }
        return x;
    }
  }