0%

leetcode 169 Majority Element || leetcode 229 Majority Element II

leetcode 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

题目地址:leetcode 169. Majority Element

题意:给定一个长度为n的数组,求其中的主要元素即出现次数大于n/2的元素。(输入数据中,解一定存在)

思路:

1.排序,复杂度O(nlogn)

1
2
3
4
5
class Solution:
# @param num, a list of integers
# @return an integer
def majorityElement(self, num):
return sorted(num)[len(num)>>1]

2.hash ,时间复杂度O(n),空间复杂度O(n)

1
2
3
4
5
6
7
8
class Solution:
# @param num, a list of integers
# @return an integer
def majorityElement(self, num):
dic ,n= collections.Counter(num),len(num)
for i,x in dic.items():
if x > (n>>1):
return i
  1. 摩尔投票(Boyer–Moore majority vote algorithm),时间复杂度O(n),空间复杂度O(1)

摩尔投票的思想是用一个计数器进行计数,当一个元素的计数为0时,替换该元素

步骤具体如下:(from wiki:  Boyer–Moore majority vote algorithm

  1. Eliminate all elements except one. Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate: If the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate.
  2. Determine if the remaining element is a valid majority element.

翻译过来就是:

  1. 维护一个候选数candidate和计数器counter。遍历数组中所有的元素, 设当前的元素为x,若 counter = 0,则 candidate = x, counter = 1; 否则, 根据candidate 与x是否相等来更新counter(相等+1,不等-1)
  2. 在遍历一次,判断候选数是否为合法的主元素。

为什么这样做是对的呢?因为若在有解的情况下,一个元素y出现>n/2次,那么要抵消掉它,必然也要有相同的元素才行,而总的元素才n个,也就是说元素y在这样的计数中不会被抵消。保证有解的情况最后的候选数就是主要元素。

代码如下:(本题中,因为一定有解,故不用进行验证候选元素是否为主元素)

C

1
2
3
4
5
6
7
8
9
10
11
int majorityElement(int* nums, int numsSize) {
int candidate=nums[0],count=1;
for(int i = 1; i < numsSize ;i++){
if(nums[i] == candidate) count++;
else if(count) count--;
else{
count = 1; candidate = nums[i];
}
}
return candidate;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
candidate = cnt = 0
for num in nums:
if candidate == num:
cnt += 1
elif cnt:
cnt -= 1
else:
candidate, cnt = num, 1
return candidate

 

leetcode 229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

题目地址:leetcode Majority Element II

题意:给定一个长度为n的数组,求其中出现次数大于 ⌊ n/3 ⌋ 的所有元素。

思路:

这题是上面那题的升级版,要求时间复杂度O(n),空间复杂度O(1),也就是不能排序、不能hash,只能用我们的摩尔投票。

首先要明确的是最多有2个解,why?   因为出现次数大于n/3,则至少有n/3+1次,若有3个解,则总数应该为 3 * (n/3+1)次,也就是 n+3 >n与题目不符。

因为可能会有两个解,所以我们需要两个候选元素a和b,以及他们相应的计数cnt_a,cnt_b

初始时将a和b任意的设置为不同的数,将cnt_a和cnt_b分别设置为0,然后遍历数组。

同样的,设当前的元素为x,

  • 若x==a 则cnt_a++
  • 若x==b则cnt_b ++
  • 若cnt_a ==0 则 a = x, cnt_a =1
  • 若cnt_b ==0 则 b = x, cnt_b =1
  • 否则 cnt_a-- , cnt_b--

最后算出来的a,b在遍历一遍数组,判断其是否真的 > n/3次

为什么这样是对的呢?

对于有2个解的情况,设解为a和b, 显然a和b不会被少于n/3个元素给抵消掉,所以2个解的情况是OK的。

那么1个解的情况呢?除了元素a(a是解)外,剩下的元素不到2n/3个(这里设为m个,m < 2n/3 ),而这m个元素中,至多有m/2个元素会抵消元素a(因为我们有两个计数的哇),换句话说,能抵消a的元素总数 <=  m/2 < n /3 ,也就是说元素a最后一定会得到保留。

对于无解的情况,最后验证了是否合法,也没问题。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums: return []
a = cnt_a = cnt_b = 0
b = 1
for num in nums:
if a == num:
cnt_a += 1
elif b == num:
cnt_b += 1
elif not cnt_a:
a, cnt_a = num, 1
elif not cnt_b:
b, cnt_b = num, 1
else:
cnt_a, cnt_b = cnt_a - 1, cnt_b - 1
return [n for n in (a, b) if nums.count(n) > len(nums) / 3]

 

本题是leetcode 169 Majority Element 和 leetcode 229 Majority Element II 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~