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)

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

3. 摩尔投票(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

Python

 

 

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

 

 

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

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

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 169 Majority Element || leetcode 229 Majority Element II
本文地址:https://www.hrwhisper.me/leetcode-169-majority-element-leetcode-229-majority-element-ii/

打赏一杯咖啡钱呗

Leetcode , , . permalink.

One thought on “leetcode 169 Majority Element || leetcode 229 Majority Element II

  1. Why is b initialized as b = 1
    in leetcode 229. Majority Element II
    Can I use a = b = None?
    I used a = b = 1.
    But I cannot pass the test case when nums = [1]

Leave a Reply

Your email address will not be published. Required fields are marked *