题目

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

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

示例 1:

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

示例 2:

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

Python解法0(利用numpy)

nums = [2,2,1,1,1,2,2]
import numpy as np
counts = np.bincount(nums)
print(np.argmax(counts))

通常为了简单起见,在Python中计算众数我们会简单的使用numpy库进行计算。注意np.bincount函数的用法,它会统计0,1,…(注意,是从0开始计数)中的每个元素的个数,然后np.argmax(counts)再统计最大的那个的脚标,也就是众数。这里局限性非常大,要默认原本的list中没有负数,不然会报错。而且LeetCode中不能调库,所以这种方法不可取。


Python解法1(暴力计算)

下面介绍两种暴力计算的方法,其实本质是一样的,用了两重的for循环,但这种暴力计算的方法非常慢,在测试的时候很可能在规定的时间内跑不出结果。

1. 直接进行暴力计算
class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        majority_count = len(nums)//2
        for num in nums:
            count = sum(1 for elem in nums if elem == num)
            if count > majority_count:
                return num
2. 利用count函数进行计算
class Solution:
    def majorityElement(self, nums):
    	n = len(nums)
		for j in nums:
    		if nums.count(j) > n / 2 : break
		return j

Python解法2(利用字典实现)

这里我们利用了Python中的字典的方法来进行实现,这里没有用到在数组中出现次数大于 n / 2 n/2 n/2的元素,这个信息,而是对一般的取众数都管用。并且速度比前面的方法还要快。

这里有个小技巧,注意dict.get(key, 0)的用法,其表示获取key对应的值,若没有,则用0来填补,这里非常巧妙。

另外则是:max(dict, key=dict.get)表示取其中最大的值(这个是上网查到的),然后,发现。。。在Python3中,max(dict)也是一样的结果,所以使用后面这个会更加方便。

class Solution:
    def majorityElement(self, nums):
        dict = {}
        for key in nums:
            dict[key] = dict.get(key, 0) + 1
        return max(dict, key=dict.get)

Python解法3(摩尔投票法)

最后这种方法非常巧妙,称为摩尔投票法。设计出这种方法的真的是一个天才,其时间复杂度为 O ( n ) O(n) O(n)。充分利用了在数组中出现次数大于 n / 2 n/2 n/2的元素这一条件。摩尔投票法是这几种方法中最快的。

具体的思想:从第一个数开始,先令count=1,遇到相同的就加1,遇到不同的就减1,减到0就重新换下个数开始计数,到最后是哪个数,那么那个数就是众数。

到这里肯定有人和我一样的疑问,假设有个数是众数,它在开始和结尾,结果在中间被一些别的数count了很多次,结尾会不会变不回来,结果当然是不会的!不信。。可以自己试试。

class Solution:
    def majorityElement(self, nums):
		major = nums[0]
		count = 1
		n = len(nums)
		del nums[0]
		for i in nums:
		    if count == 0:
		        count += 1
		        major = i
		    elif major == i:
		        count += 1
		    else:
		        count -= 1
		return major

题目网址:https://leetcode-cn.com/problems/majority-element/

Logo

有“AI”的1024 = 2048,欢迎大家加入2048 AI社区

更多推荐