JAVA 牛牛

169. 多数元素

  • Mar 25, 2020
  • 0 views
  • 难度：简单
  • 本题涉及算法： 排序 哈希表 摩尔投票法思路
  • 思路： 排序 哈希表 摩尔投票法思路
  • 类似题型:

题目 169. 多数元素

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

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

示例

示例 1:

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

示例 2:

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

方法一

解题思路

  • 一定会出现多数元素，则说明，在排序后，中间位置一定是该元素
  • 时间复杂度 $O(logn)$ 空间复杂度 $O(nlogn)$

pic1

代码

python

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

java

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

方法二 哈希表

  • 通过使用哈希表保存所有元素出现的次
  • 在哈希表中找出出现 大于 n/2 的数
  • 时间复杂度 $O(n)$ 空间复杂度 $O(n)$

java

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

python

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {}
        for i in nums:
            if dic.get(i):
                v = dic.values()
                dic[i]+=1
            else:
                dic[i]=1
        for di in dic:
            if dic.get(di)>(len(nums)/2):
                return di

方法三 摩尔投票法思路 (投票法)

  • 候选人(cand_num)初始化为 nums[0]，票数 count 初始化为1。
  • 当遇到与 cand_num 相同的数，则票数 count = count + 1 ，否则票数 count = count - 1。
  • 当票数 count 为0时，更换候选人，并将票数 count 重置为1。
  • 遍历完数组后，cand_num 即为最终答案。

为何这行得通呢？

  • 投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。
  • 且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。
  • 因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。
  • 这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。

无论数组是 1 2 1 2 1，亦或是 1 2 2 1 1，总能得到正确的候选人。

java

class Solution {
    public int majorityElement(int[] nums) {
        int cand_num = nums[0], count = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (cand_num == nums[i])
                ++count;
            else if (--count == 0) { // 很鸡贼的一段代码 --count 是不是等于 0， 先减1 在说
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
}
Search