题目描述

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

样例描述

Example 1:

Input: nums = [3,2,3]
Output: 3
Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2
 

Constraints:

n == nums.length
1 <= n <= 5 * 104
-231 <= nums[i] <= 231 - 1

思路

1. 由题设，肯定存在一个数大于总数的一半。将这个最多的数看成“炸弹”，cnt记录炸弹的个数，val记录哪个数是炸弹。遍历数组时，若下一个数和当前val一样，cnt就增加1，即想象成炸弹的数量增加1。若不一样，想象成消耗一个炸弹毁掉不一样的那个数。然后继续遍历。这样到最后剩余的肯定是炸弹。
2. 注意若 cnt=0，则选取下一个数作为val，由题目肯定是存在这样一个数的，所以最后val必然是这个数。

代码

class Solution {
    public int majorityElement(int[] nums) {
           int cnt = 0, val = 0;
           for (int x: nums){
               if (cnt == 0){
                   val = x;
                   cnt ++;
               }
               else{
                   if (x ==val) cnt ++;
                   else cnt --;
               }
           }
           return val;
    }
}