Leetcode Tencent 50 Task8 169. Majority Element

Posted on In Views: Disqus:
DataWhale暑期学习小组-LeetCode刷题第八期Task8。

描述

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

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：169. Majority Element

解题思路

本题依然是考察位运算，如果没有这个提示，很容易想到用一个map<key,value>来求解，其中key为数组当中出现过的去重元素，value是对应元素出现过的次数，这样遍历一遍数组就可以求得这个map，然后找出value大于 ⌊ n/2 ⌋的那一个键值对，返回key。这个方法倒是能够在O(N)的时间复杂度内求解问题，但是需要开辟额外的空间。另外一种比较容易想到的办法是用两重循环，第一重遍历数组，第二重对数组中元素出现的次数进行计数，然后最后取出count> ⌊ n/2 ⌋的那个元素。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int majorityElement(int* nums, int numsSize){
    int major = numsSize / 2;
    
    for(int i = 0; i<numsSize; i++)
    {
        int count = 0;
    
        for(int j = 0; j<numsSize; j++)
        {
            if(nums[j] == nums[i]){
                count++;
            }
            
        }
        if(count > major)
            return nums[i];
    }
    
    return 0;

}

不过非常遗憾，超时了……44个测试用例通过了42个，卡在了第43个。根据题目归类，同样应该还有采用位运算的更加优雅的算法。

首先来理解下面这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
int main(int argc, char const *argv[])
{
	/* code */
	int num = 63;
	for (int i = 0; i < 32; ++i)
	{
		/* code */
		printf("%d %d\n", i, num & (1 << i));

	}
	return 0;
}

运行输出为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
0 1
1 2
2 4
3 8
4 16
5 32
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0
31 0

不难发现，我们用num & (1 << i)这串用于取得整数num二进制第i位是否为1，若为1则返回该位为1右侧补i-1个0的整数的位操作，将num分拆为一系列用类似整数表示整数子串，以上面的代码为例：

63=32(25)+16(24)+8(23)+4(22)+2(21)+1(20)63=32(2^5)+16(2^4)+8(2^3)+4(2^2)+2(2^1)+1(2^0)

于是，我们的思路来了，能否将题目中所需要寻找的众数也进行这样的分拆，用位来进行表示，然后判断它从0～31位上面是0或者是1。将众数二进制位串位数记位i，那现在的问题就转换为从0～31遍历i的时候，通过题目透露的众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素这个条件来判断第i位是0或者是1。从上面的例子可以看出，如果第i位是1，则num & (1 << i)不等于0，这里我们可以遍历整个数组，设置两个计数器count_1、count_0，分别统计不等于0出现的次数和等于0出现的次数，根据众数的定义，比较这两个计算器的大小，count_1大则意味着众数该位为1，否则为0。最后将遍历i的结果累加便得到了所要求的众数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int majorityElement(int* nums, int numsSize){
    int result = 0;
    
    for(int i = 0; i<32; i++)
    {
		  int count_1 = 0, count_0 = 0;    
        for(int j = 0; j<numsSize; j++)
        {
            if((nums[j] & (UINT32_C(1) << i)) != 0)
            {
                count_1++;
            }
            else
            	count_0++;
            
        }
        if(count_1 > count_0)
            result |= (UINT32_C(1) << i);
    }
    
    return result;

}