CTF of Z2BNS
0%

多数元素

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 4.1k 阅读时长 ≈ 4 分钟

题目地址

难度：⭐

题目描述：

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

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

示例1：

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

示例2：

1
2
输入: [2,2,1,1,1,2,2]
输出: 2
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

统计数组中的元素出现次数存储到map中，然后遍历map返回出现次数大于n/2的元素。

c++代码：(执行用时28ms，击败55.10%，内存消耗9.1M，击败5.18%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> m;
        int n=nums.size()/2;
        for(int i:nums){
            ++m[i];
        }
        for(auto [j,k]:m){
            if(k>n){
                return j;
            }
        }
        return 0;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

说明
本题题面中没有给出数据范围，但最简单的暴力方法（即枚举数组中的每个元素，再遍历一遍数组统计其出现次数，时间复杂度为 $O(N^2)$ 的算法）会超出时间限制，因此我们需要找出时间复杂度小于 $O(N^2)$的优秀做法。

方法一：哈希表
思路

我们知道出现次数最多的元素大于 $\lfloor \dfrac{n}{2} \rfloor$ 次，所以可以用哈希表来快速统计每个元素出现的次数。

算法

我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。

我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

c++代码：(执行用时40ms，击败35.16%，内存消耗8.9M，击败61.00%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度。我们遍历数组 nums 一次，对于 nums 中的每一个元素，将其插入哈希表都只需要常数时间。如果在遍历时没有维护最大值，在遍历结束后还需要对哈希表进行遍历，因为哈希表中占用的空间为 $O(n)$（可参考下文的空间复杂度分析），那么遍历的时间不会超过 $O(n$)。因此总时间复杂度为 $O(n)$。

  • 空间复杂度：$O(n)$。哈希表最多包含 $n - \lfloor \dfrac{n}{2} \rfloor$ 个键值对，所以占用的空间为 $O(n)$。这是因为任意一个长度为 $n$ 的数组最多只能包含 $n$ 个不同的值，但题中保证 nums 一定有一个众数，会占用（最少） $\lfloor \dfrac{n}{2} \rfloor + 1$个数字。因此最多有 $n - (\lfloor \dfrac{n}{2} \rfloor + 1)$个不同的其他数字，所以最多有 $n - \lfloor \dfrac{n}{2} \rfloor$个不同的元素。

方法二：排序
思路

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 $\lfloor \dfrac{n}{2} \rfloor$ 的元素（下标从 0 开始）一定是众数。

算法

对于这种算法，我们先将 nums 数组排序，然后返回上文所说的下标对应的元素。下面的图中解释了为什么这种策略是有效的。在下图中，第一个例子是 $n$ 为奇数的情况，第二个例子是 $n$ 为偶数的情况。

image.png

对于每种情况，数组下面的线表示如果众数是数组中的最小值时覆盖的下标，数组下面的线表示如果众数是数组中的最大值时覆盖的下标。对于其他的情况，这条线会在这两种极端情况的中间。对于这两种极端情况，它们会在下标为 $\lfloor \dfrac{n}{2} \rfloor$ 的地方有重叠。因此，无论众数是多少，返回 $\lfloor \dfrac{n}{2} \rfloor$ 下标对应的值都是正确的。

c++代码：

1
2
3
4
5
6
7
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

复杂度分析

时间复杂度：$O(n\log n)$。将数组排序的时间复杂度为 $O(n\log n)$。

空间复杂度：$O(\log n)$。如果使用语言自带的排序算法，需要使用 $O(\log n)$ 的栈空间。如果自己编写堆排序，则只需要使用 $O(1)$ 的额外空间。

方法三：随机化
思路

因为超过 $\lfloor \dfrac{n}{2} \rfloor$ 的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数。

算法

由于一个给定的下标对应的数字很有可能是众数，我们随机挑选一个下标，检查它是否是众数，如果是就返回，否则继续随机挑选。

c++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        while (true) {
            int candidate = nums[rand() % nums.size()];
            int count = 0;
            for (int num : nums)
                if (num == candidate)
                    ++count;
            if (count > nums.size() / 2)
                return candidate;
        }
        return -1;
    }
};

复杂度分析

  • 时间复杂度：理论上最坏情况下的时间复杂度为 $O(\infty)$，因为如果我们的语气很差，这个算法会一直找不到众数，随机挑选无穷多次，所以最坏时间复杂度是没有上限的。然而，运行的期望时间是线性的。为了更简单地分析，先说服你自己：由于众数占据 超过 数组一半的位置，期望的随机次数会小于众数占据数组恰好一半的情况。因此，我们可以计算随机的期望次数（下标为 prob 为原问题，mod 为众数恰好占据数组一半数目的问题）：

计算方法为：当众数恰好占据数组的一半时，第一次随机我们有 $\frac{1}{2}$ 的概率找到众数，如果没有找到，则第二次随机时，包含上一次我们有 $\frac{1}{4}$的概率找到众数，以此类推。因此期望的次数为 $i * \frac{1}{2^i}$的和，可以计算出这个和为 $2$，说明期望的随机次数是常数。每一次随机后，我们需要 $O(n)$的时间判断这个数是否为众数，因此期望的时间复杂度为 $O(n)$。

  • 空间复杂度：$O(1)$。随机方法只需要常数级别的额外空间。

方法四：分治
思路f

如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。

我们可以使用反证法来证明这个结论。假设 a 既不是左半部分的众数，也不是右半部分的众数，那么 a 出现的次数少于 l / 2 + r / 2 次，其中 l 和 r 分别是左半部分和右半部分的长度。由于 l / 2 + r / 2 <= (l + r) / 2，说明 a 也不是数组 nums 的众数，因此出现了矛盾。所以这个结论是正确的。

这样以来，我们就可以使用分治法解决这个问题：将数组分成左右两部分，分别求出左半部分的众数 a1 以及右半部分的众数 a2，随后在 a1 和 a2 中选出正确的众数。

算法

我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

c++代码：

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
class Solution {
    int count_in_range(vector<int>& nums, int target, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; ++i)
            if (nums[i] == target)
                ++count;
        return count;
    }
    int majority_element_rec(vector<int>& nums, int lo, int hi) {
        if (lo == hi)
            return nums[lo];
        int mid = (lo + hi) / 2;
        int left_majority = majority_element_rec(nums, lo, mid);
        int right_majority = majority_element_rec(nums, mid + 1, hi);
        if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2)
            return left_majority;
        if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2)
            return right_majority;
        return -1;
    }
public:
    int majorityElement(vector<int>& nums) {
        return majority_element_rec(nums, 0, nums.size() - 1);
    }
};

复杂度分析

  • 时间复杂度：$O(n\log n)$。函数 majority_element_rec() 会求解 2 个长度为 $\dfrac{n}{2}$ 的子问题，并做两遍长度为 $n$ 的线性扫描。因此，分治算法的时间复杂度可以表示为：

根据 主定理，本题满足第二种情况，所以时间复杂度可以表示为：

  • 空间复杂度：$O(\log n)$。尽管分治算法没有直接分配额外的数组空间，但在递归的过程中使用了额外的栈空间。算法每次将数组从中间分成两部分，所以数组长度变为 1 之前需要进行 $O(\log n)$次递归，即空间复杂度为 $O(\log n)$。

方法五：Boyer-Moore 投票算法
思路

如果我们把众数记为 $+1$，把其他数记为 $-1$，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

算法

Boyer-Moore 算法的本质和方法四中的分治十分类似。我们首先给出 Boyer-Moore 算法的详细步骤：

  • 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；

  • 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：

    • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
  • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
  • 在遍历完成后，candidate 即为整个数组的众数。

c++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$。Boyer-Moore 算法只对数组进行了一次遍历。
  • 空间复杂度：$O(1)$。Boyer-Moore 算法只需要常数级别的额外空间。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

我giao你哥，官方题解给出5种解题方法，以后再补吧，罢了罢了想了想还是写完吧，拒绝拖延，从我做起🙄。

官方题解方法一哈希表和我的方法是一样的，不过其中认为遍历数组nums时维护最大值省去了对哈希映射的遍历这点我不敢苟同，因为这样做对数组nums中的每一个元素（相同的元素有多个也要遍历多次）都要进行if结构判断（遍历了n次），而遍历哈希映射最多只遍历不同元素个数（ $\frac{n}{2}-1$次），而且不需要维护最大值，只需要元素次数大于$\frac{n}{2}$就可以了。

第二种方法效率不行，后三种这么复杂不会真的有人用吧，最后一种还好些，更多的内容去官方题解找（我只复制了一部分）。

------------- THE END! THANKS! -------------