Leetcode-169. 求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

解法：这里我推荐使用sorting和hashtable的方法来进行解决。Sorting的时间复杂度是O（NlogN），空间复杂度为O（1），但是代码非常的简洁；hashtable的时间复杂度是O（N），因为要遍历所有的元素，空间复杂度也是O（N）

Sorting

• Java

class Solution {
   
    public int majorityElement(int[] nums) {
   
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

• Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums)//2]

HashTable

• Java

class Solution {
   
    public int majorityElement(int[] nums) {
   
        Map<Integer,Integer> mp = new HashMap<>();
        int res = 0;
        for(int num:nums){
   
            if(!mp.containsKey(num)){
   
                mp.put(num,1);
            }else{
   
                mp.put(num,mp.get(num)+1);
            }
            if(mp.get(num)>(nums.length/2)){
   
                res = num;
                break;
            }
        }
        return res;
    }
}

• Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        mp = {
   }
        res = 0
        for num in nums:
            if not num in mp:
                mp[num] = 1
            else:
                mp[num] += 1
            if mp[num]>len(nums)//2: 
                res = num
                break
        return res