题目：

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

也就是找数组中出现次数大于一半的数字，题目保证这个数字存在。

方法一：位操作

针对数组中每一个数的每一位，计算每一位上0和1出现的次数，取出现多的作为最终数字的当前位。

代码如下：时间复杂度32n=O(n)，空间复杂度O(1)

// bit操作    public int majorityElement(int[] nums) {        int temp = 0, ans = 0, count0 = 0, count1 = 0;        for (int i = 0; i < 32; i++) {            count0 = 0;            count1 = 0;            for (int j = 0; j < nums.length; j++) {                if (((nums[j] >>> i) & 1) == 1)                    count1++;                else                    count0++;            }            if (count1 > count0)                temp += 1;            if (i < 31)                temp >>>= 1;        }        for (int i = 0; i < 32; i++) {            ans += ((temp >> i) & 1);            if (i < 31)                ans <<= 1;        }        return temp;    }

 

方法二：HashMap，

空间复杂度O(n),时间复杂度O(n),相对位操作更耗时。

// 使用hashMap    public int majorityElement(int[] nums) {        int temp = 0, ans = 0, count0 = 0, count1 = 0;        Map
     
       countMap = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            countMap.put(nums[i], countMap.getOrDefault(nums[i], 0) + 1);            if (countMap.get(nums[i]) > nums.length / 2)                return nums[i];        }        return 0;    }
     

方法三：计数法，

这个方法应该是最优解法吧。相比位操作更好。

该方法的思路是从局部思考问题，前2K个数字中，某个数无法做成majority element，但它也有可能出现很多次，但是最终在某个点上会被其他不相同的数字中和了。从后面再计数。最终找到的就是majority element。（描述的不好，直接看代码理解吧）。

假设被中和的是majority element，不用担心，因为你干掉了和你一样多的对手，在后续的子数组中，你还是大头。

假设被中和的不是，那么后续子数组中，你还是不能。

代码如下：

public int majorityElement(int[] nums) {        int count = 0;        int ans = nums[0];        for (int i : nums) {            if (count == 0)                ans = nums[i];            if (ans == nums[i])                count++;            else                count--;        }        return ans;    }