leetcode:169. 多数元素

169. 多数元素

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/majority-element/

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

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= $5\ast 10^4$
• $-10^9$ <= nums[i] <= $10^9$

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

解法

• 哈希表： 哈希表统计出现次数，如果大于半数则返回该元素
• 排序 ： 排序后中间元素肯定是众数
• Boyer-Moore 投票算法：
  • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1
  • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1
• 分治法： 分两部分，然后比较两部分返回的众数

代码实现

哈希表

python实现

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)

        if n == 1:
            return nums[0]

        counts = dict()

        for num in nums:
            if num in counts:
                counts[num] += 1
            else:
                counts[num] = 1
            
            if counts[num] > n // 2:
                return num
        return None

c++实现

class Solution {
    
public:
    int majorityElement(vector<int>& nums) {
    
        int n = nums.size();
        if (n == 1) return nums[0];

        unordered_map<int, int> counts;
        for(int num: nums) {
    
            auto it = counts.find(num);
            if (it != counts.end())
                counts[num]++;
            else
                counts[num] = 1;
            
            if (counts[num] > n/2)
                return num;
        }
        return -1;
    }
};

复杂度分析

• 时间复杂度： $O(n)$
• 空间复杂度： $O(n)$

排序

python实现

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

c++实现

class Solution {
    
public:
    int majorityElement(vector<int>& nums) {
    
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};

复杂度分析

• 时间复杂度： $O(nlogn)$
• 空间复杂度： $O(logn)$

投票法

python实现

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 1
        item = nums[0]
        for num in nums[1:]:
            if item == num:
                count += 1
            else:
                count -= 1
                if count == 0:
                    item = num  # 变成新的元素
                    count = 1  # 新的计数
        return item

c++实现

class Solution {
    
public:
    int majorityElement(vector<int>& nums) {
    
        int n = nums.size();
        if (n == 0)
            return nums[0];
        
        int item = nums[0];
        int count = 1;
        for (int i=1; i<n; i++) {
    
            if (nums[i] == item)
                count++;
            else {
    
                count--;
                if (count == 0) {
    
                    item = nums[i];
                    count = 1;
                }
            }
        }
        return item;
    }
};

复杂度分析

• 时间复杂度： $O(n)$
• 空间复杂度： $O(1)$

分治递归

python实现

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        
        def helper(l, h):
            if l == h:
                return nums[l]
            
            mid = l + (h-l)//2
            left_num = helper(l, mid)
            right_num = helper(mid+1, h)
            if left_num == right_num:
                return left_num
            
            left_count = sum(1 for i in range(l, h+1) if nums[i] == left_num)
            right_count = sum(1 for i in range(l, h+1) if nums[i] == right_num)
            return left_num if left_count > right_count else right_num
        
        return helper(0, n-1)

c++实现

class Solution {
    
public:

    int helper(vector<int>& nums, int low, int high) {
    
        if (low == high) return nums[low];

        int mid = low + (high-low) / 2;
        int left_num = helper(nums, low, mid);
        int right_num = helper(nums, mid+1, high);

        if (left_num == right_num)
            return left_num;
        
        int left_count = 0, right_count = 0;
        for (int i=0; i<high+1; i++) {
    
            if (nums[i] == left_num)
                left_count++;
            if (nums[i] == right_num)
                right_count++;
        }
        return left_count > right_count ? left_num : right_num;
    }

    int majorityElement(vector<int>& nums) {
    
        int n = nums.size();
        return helper(nums, 0, n-1);
    }
};

复杂度分析

• 时间复杂度： $O(nlogn)$
• 空间复杂度： $O(logn)$

参考

• https://leetcode.cn/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/