Leetcode169——多数元素

——数组中出现次数超过一半的数字

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

链接：Leetcode169

示例 1：
**输入：**nums = [3,2,3] **输出：**3
示例 2：
**输入：**nums = [2,2,1,1,1,2,2] **输出：**2

数据范围：_n _≤ 50000，
数组中元素的值 版本1：0 ≤_val_≤10000
版本2：-109 <= nums[i] <= 109
要求：空间复杂度：O(1)，时间复杂度 O(n)

核心代码模式

//参数说明
//nums指向目标数组
//numsSize对应数组大小
//返回值就是找到的多数元素
int majorityElement(int* nums, int numsSize)
{
    
}
1
2
3
4
5
6
7
8

思路分析（C语言）

1.哈希数组法

这里其实只是用到了其思想，并没有真的使用哈希表（还没学呢），使用C语言中的变长数组来作为表。
这个表是用来干什么的呢？用来计数的，其下标对应某数字，数组内容对应某数字出现次数，假设创建了cnt数组，比如cnt[1]的值为2表示1这个数字出现了两次。那这个表的大小由什么决定呢？得看下标能到哪个数吧，也就是要统计的数据中最大的那个数的大小作为表的大小是吗？还得加个1，因为数组下标从0开始，不加1的话就不能把cnt[max]最大的那个数包括进去了。实际上这只适用于版本1的要求，因为版本2中还出现了负数，数组下标一般不能为负数，那要是要满足版本2的要求又该咋整呢？其实不出现负数很简单，只需创建映射关系。

如何创建映射关系？
首先，我们得算一算最小的数（min）和最大的数（max）的绝对值哪个更大一些，取较大者设为size，那这样就可以建立映射关系：让每个下标都加上一个size。
如图：

这样一来下标就不会出现负数了，原来的负数都对应上了某个正数。
同时我们也确定了数组应该要多大：2*size+1。（一半给负数，一半给正数，中间的给0）

代码实现

int majorityElement(int* nums, int numsSize)
{    
    int i = 0;
    int max = 0;
    int min = 0;
    int ret = 0;
    
    for(i = 0; i < numsSize; i++)
    {
        if(nums[i] > max)
            max = nums[i];
        if(nums[i] < min)
            min = nums[i];
    }

    int size = max>abs(min) ? max : abs(min);
    int cnt[2*size + 1];
    memset(cnt, 0, (2*size+1)*sizeof(int));
    
    for(i = 0; i < numsSize; i++)
    {
        cnt[nums[i] + size]++;
        if(cnt[nums[i] + size] > numsSize / 2)
        {
            ret = nums[i];
            break;
        }
    }

    return ret;
}
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

2.摩尔投票法

在选举负责人的时候，组织方就说咱们来投票选人吧，这样公平（是否公平我们不谈），现在就开始吧~
候选人(cand_num)初始化为nums[0]，票数count初始化为1。
当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
当票数count为0时，更换候选人，并将票数count重置为1。
遍历完数组后，cand_num即为最终答案。

为何这行得通呢？
投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。
且“多数元素”的个数> ⌊ n/2 ⌋，其余元素的个数总和<= ⌊ n/2 ⌋。
因此“多数元素”的个数减去其余元素的个数总和，结果肯定 >= 1。
这就相当于每个“多数元素”和其他元素两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。
比如无论数组是1 2 1 2 1，亦或是1 2 2 1 1，总能得到正确的候选人。

代码实现

int majorityElement(int* nums, int numsSize)
{
    int cand_num = nums[0];
    int count = 1;
    int i = 0;
    
    for(i = 1; i < numsSize; i++)
    {
        if(cand_num == nums[i])
            count++;
        else if(--num == 0)
        {
            cand_num = nums[i];
            count = 1;
        } 
    }
    return cand_num;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

同时还可以这么理解：诸侯争霸赛
有几个诸侯在争夺霸权打起来了，假设每个诸侯手下的军队每个人去干仗都能一对一同归于尽，那这么说就是比拼人数了。最后还有人活下来的国家就是胜利者。
各步骤的解释放在注释里了，直接看代码吧。

代码实现

int majorityElement(int* nums, int numsSize)
{
    // 诸侯争霸赛
    int king = nums[0];  // 我先来做霸王
    int cnt = 1;         // 我就一个人
    
    for (int i = 1; i < nunsSize; i++)
    {
        if (cnt > 0)	// 战斗到最后一兵一卒
        {  
            if (nums[i] == king) //战友来了
            {  
                cnt++;
            } else 	//与敌军1v1一次拼死一个战士
            {  
                cnt--;
            }
        } 
        else //全部牺牲，改朝换代
        {  
            king = nums[i];
            cnt = 1;
        }
    }
    
    //人数最多的站（笑）到了最后
    return king;
}
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

3.排序取中值法

你想啊，题目说了，一定存在某个数，它的个数是大于等于n/2的，也就是说数组里面一半以上的数字都是它，那不管数组里面的元素怎样分布都好，只要把数组按照升序或者降序排好序后，这个“多数元素”一定会出现在中间位置，因为排完序后所有相同的元素都是相邻的，即使是从数组边上开始放数字，“多数元素”最起码会出现在中间。
比如数组：5，0，5，2，5，4，4，5，8，9，5，5，按升序排好后得到0，2，4，4，5，5，5，5，5，5，8，9中间位置就是5。
所以说，我们只要把数组排好序，中间元素一定就是“多数元素”了，这不就很简单了嘛，直接快排qsort函数整起来~😆

代码实现

int CmpInt(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}

int majorityElement(int* nums, int numsSize)
{
    qsort(nums, numsSize, sizeof(int), CmpInt);
    return nums[numsSize / 2];
}
1
2
3
4
5
6
7
8
9
10