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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

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

思路：

  • 通过hash的key|value进行对应统计票数，最后将得票数进行比较，选出最大得票数的key，进行返回。

    class Solution {
  public int majorityElement(int[] nums) {
      Map<Integer,Integer> map = new HashMap<>();
      for(int i=0;i<nums.length;i++){
          if(map.containsKey(nums[i])){
              int count = map.get(nums[i])+1;
              map.put(nums[i],count);
          }else{
              map.put(nums[i],1);
          }
      }
      for(Map.Entry<Integer, Integer> entry : map.entrySet()){
          if(entry.getValue()>(nums.length/2)){
              return entry.getKey();
          }
      }
      return 0;
  }
}

  • 利用众数超过数组半数的特点，进行相抵消。

    class Solution {
  public int majorityElement(int[] nums) {
      // 因为要求过半数,所以可以将不同数相抵，如果最后得到一定是重复超过数组一般的数
      int votes=0;
      int x = 0;
      for(int i : nums){
          if(votes==0) x = i;
          votes += (x==i?1:-1);
      }
      return x;
  }
}