【LeetCode】求众数(四种方法)
题目给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于n/2n/2n/2的元素。你可以假设数组是非空的,并且给定的数组总是存在众数。示例 1:输入: [3,2,3]输出: 3示例 2:输入: [2,2,1,1,1,2,2]输出: 2...
题目
给定一个大小为 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
更多推荐
所有评论(0)