细语呢喃

技术改变生活

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/

请我喝杯咖啡吧~