专栏首页算法码上来【每日算法Day 90】5种方法:求解数组中出现次数超过一半的那个数

【每日算法Day 90】5种方法:求解数组中出现次数超过一半的那个数

论文中了,非常感谢各位的支持!

题目链接

LeetCode 面试题39. 数组中出现次数超过一半的数字[1]

题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

说明:

  • 1 <= 数组长度 <= 50000

示例1

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

题解

哈希表

这个方法最简单,用哈希表记录每个数字出现的次数,最后看哪个数字次数超过一半就行了。

时间复杂度 ,空间复杂度 。

排序

对数组从小到大进行排序,那么众数一定在 nums[n/2] 处。为什么呢?

因为排序后相同的数都连续了,所以众数最左端的极限情况就是从下标 0 开始往后排,那么因为超过了一半,所以尾部下标一定会超过 n/2 。而最右端的极限情况就是从下标 n-1 往前排,因为超过了一半,所以头部下标也会在 n/2 之前。

综上,众数所在的区间一定会包含下标 n/2

时间复杂度 ,空间复杂度 。

随机采样

其实我第一个想到的方法反而是这个反常规的随机采样方法。因为众数超过了一半,所以采样大概率会采到这个众数。

那么我们随机采样一个数,然后遍历一遍数组看它的个数。如果个数超过了一半就是它了,否则继续采样,直到采到众数。

平均时间复杂度 ,空间复杂度 。

分治

如果把区间 [0, n-1] 平均分成两半,那么我们可以证明,原来的众数在某一半区间里依然是众数。

为什么呢?反证法,假设两半区间的众数都不是原来的众数,那么在左半区间原来的众数一定小于一半,右半区间也是的。加起来之后总数一定小于一半的,和条件是矛盾的。

所以我们递归求解两半区间的众数,然后看哪个数出现次数较多,众数就是它了。

时间复杂度 ,空间复杂度 。

摩尔投票

这个方法我一开始也想到了,但是没有想到这竟然有理论解释,而且是大名鼎鼎的摩尔投票算法。

它的主要步骤是这样的:

  • 初始化两个变量, cand 表示候选人,cnt 表示赞同它的票数。
  • 如果 cnt = 0,那么 cand 就设置为当前的数字。
  • 如果 cand 等于当前数字,那么票数 cnt 加一,否则票数减一。
  • 最后 cand 就是得票超过一半的众数。

严格证明比较复杂,是一篇论文,这里说个比较好理解的思路:

  • 如果当前候选人是众数,那么其他的众数会支持自己,其他的数反对自己。但是因为众数超过了一半,所以众数最后一定会当选。
  • 如果当前候选人不是众数,那么就惨了,其他的数和众数全都会反对他。那反对票远远超过一半了,肯定会下台,然后换候选人。
  • 上面两种情况会在 cnt = 0 的时刻进行转换,也就是换候选人。

时间复杂度 ,空间复杂度 。

代码

哈希表(c++)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mp;
        for (auto x : nums) mp[x]++;
        for (auto [k, v] : mp) {
            if (v > n/2) return k;
        }
        return -1;
    }
};

排序(c++)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        return nums[n/2];
    }
};

随机采样(c++)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        while (1) {
            int idx = rand() % n;
            int cnt = 0;
            for (auto x : nums) {
                if (x == nums[idx]) cnt++;
            }
            if (cnt > n/2) return nums[idx];
        }
        return -1;
    }
};

分治(c++)

class Solution {
public:
    int numCount(vector<int>& nums, int x, int l, int r) {
        int cnt = 0;
        for (int i = l; i <= r; ++i) {
            if (nums[i] == x) cnt++;
        }
        return cnt;
    }

    int findMajority(vector<int>& nums, int l, int r) {
        if (l == r) return nums[l];
        int m = l+(r-l)/2;
        int ml = findMajority(nums, l, m);
        int mr = findMajority(nums, m+1, r);
        if (ml == mr) return ml;
        int cl = numCount(nums, ml, l, r);
        int cr = numCount(nums, mr, l, r);
        return cl < cr ? mr : ml;
    }

    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        return findMajority(nums, 0, n-1);
    }
};

摩尔投票(c++)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cand = 0, cnt = 0;
        for (auto x : nums) {
            if (!cnt) cand = x;
            if (x == cand) cnt++;
            else cnt--;
        }
        return cand;
    }
};

哈希表(python)

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

排序(python)

class Solution:
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)//2]

随机采样(python)

import random

class Solution:
    def majorityElement(self, nums):
        majority_count = len(nums)//2
        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

分治(python)

class Solution:
    def majorityElement(self, nums, lo=0, hi=None):
        def majority_element_rec(lo, hi):
            if lo == hi:
                return nums[lo]
            mid = (hi-lo)//2+lo
            left = majority_element_rec(lo, mid)
            right = majority_element_rec(mid+1, hi)
            if left == right:
                return left
            left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)
            right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)
            return left if left_count > right_count else right
        return majority_element_rec(0, len(nums)-1)

摩尔投票(python)

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)
        return candidate

关注【算法码上来】,每日算法干货马上就来!

参考资料

[1]

LeetCode 面试题39. 数组中出现次数超过一半的数字: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法系列【LeetCode 719】找出第 k 小的距离对

    给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

    godweiyang
  • 【每日算法Day 82】面试经典题:求第K大数,我写了11种实现,不来看看吗?

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    godweiyang
  • 每日算法系列【LeetCode 1250】检查「好数组」

    给你一个正整数数组 nums ,你需要从中任选一些子集,然后将子集中每一个数乘以一个任意整数,并求出他们的和。

    godweiyang
  • c++ LeetCode(初级数组篇)十一道算法例题代码详解(一)

    原文链接:https://www.cnblogs.com/DOMLX/p/10940636.html

    徐飞机
  • 剑指offer java版(一)

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

    蜻蜓队长
  • Array - 164. Maximum Gap

    Given an unsorted array, find the maximum difference between the successive elem...

    用户5705150
  • 2019 第十届蓝桥杯C/C++ 省赛B组题解

    又是一年一度的蓝桥杯,这次也应该是我大学最后一次学科竞赛了,今年的省赛题型和往届有些不同,代码填空没有了,只有结果填空和编程大题,不过坑还是一样的多,稍不注意就...

    指点
  • 算法:HashTable、List、Map、Set-实战

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    营琪
  • LeetCode 324. 摆动排序 II

    给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

    Michael阿明
  • Leetcode 41. First Missing Positive

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan

扫码关注云+社区

领取腾讯云代金券