算法练习5——多数元素

LeetCode 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

蛮力法

1. 双重循环，不过会超时

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        times = 0
        for i in nums:
            for j in nums:
                if i == j:
                    times += 1
            if times > len(nums) / 2:
                return i
            times = 0
1
2
3
4
5
6
7
8
9
10

2. 随机抽取，随机抽取一个元素为过半众数的概率大于1/2，该方法是基于数据特点对双重循环进行优化

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majority_count = len(nums) // 2
        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/majority-element/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12

3. 哈希表计数

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/majority-element/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9

数学方法，基于数据特征

1. Boyer-Moore 投票算法
   过半众数是数组中出现次数最多的数据，如果每次从数组中抽取两个不同的数据，最后数组中剩下的一定是众数。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        item, times = nums[0], 1
        for idx in range(1, len(nums)):
            if nums[idx] != item:
                if times > 0:
                    times -= 1
                else:
                    item = nums[idx]
                    times = 1
            else:
                times += 1
        return item
1
2
3
4
5
6
7
8
9
10
11
12
13

还是官方写的简洁啊

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/majority-element/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 排序取中间值
   过半众数排序后，n/2位置处数据一定是过半众数

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

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/majority-element/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9