写在前面
以后刷lc就逐渐往C++上迁移了, 虽然Python很香, 但是毕竟还是封装层次太高了, 但是真的是
由奢入俭难啊..
这次看一下lc的一道面试题:剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣（LeetCode）; 169. 多数元素;
看似简单题, 实则暗藏玄机, 就连官方题解都有五种之多, 下面的评论中也给出了很多很好理解的算法, 一起来看看:
题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
限制：
1 <= 数组长度 <= 50000
分析
哈希
这里我首先想到的当然是哈希, 毕竟简单题, python一行(return sorted(Counter(nums).items(), key=lambda x:x[1])[-1][0]), 用C++就要写一段了:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> s{};
int n = nums.size(), half = n / 2;
for (int i{}; i < n; ++i) {
s[nums[i]] += 1;
if (s[nums[i]] > half) return nums[i];
}
return -1;
}
但是占用了额外空间, 并且运行效率很低:
执行用时：24 ms, 在所有 C++ 提交中击败了12.48%的用户
内存消耗：18.4 MB, 在所有 C++ 提交中击败了15.01%的用户
排序
这里有个不错的思路, 不需要占用空间, 直接排序之后取中间的值即可, 原理也很好想, 因为次数超过一般的数组元素, 其必然出现在下标为n//2(下取整)的位置, 证明:
极端假设:
该数连续(因为已排好序)出现在数组左端:
数组长度为偶数(
n=6为例, 下标half=3): \(\text{元素:}\ \overline{11}\underline{\overline{11}23}\\ \text{下标:}\ 012345\)数组长度为奇数(
n=7为例, 下标half=3): \(\text{元素:}\ \overline{111}\underline{\overline{1}234}\\ \text{下标:}\ 0123456\)右端, 同理.
因为对于两端的极限情况都满足, 所以对于出现在任意位置的该数, 都可以通过下标$\lfloor n/2\rfloor$找到.
代码:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
此时复杂度下降(毕竟排序的平均复杂度是对数线性):
执行用时：16 ms, 在所有 C++ 提交中击败了65.16%的用户
内存消耗：18.3 MB, 在所有 C++ 提交中击败了60.90%的用户
但是调用排序API的话(默认是快排)会用到栈空间(递归), 所以还是有内存消耗, 官解说的是自己手写堆排序, 下面给出代码: (需要写成非递归才能保证空间复杂度为$O(1)$)
class Solution {
public:
void Max_Heapify(vector<int> &arr, int len, int i) {
bool done = false;
while (!done) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < len && arr[l] > arr[largest]) largest = l;
if (r < len && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
i = largest;
} else
done = true;
}
}
void Heap_Sort(vector<int> &arr) {
int n = arr.size();
for (int i = n / 2; i >= 0; --i) Max_Heapify(arr, n, i);
for (int i = n - 1; i >= 1; --i) {
swap(arr[0], arr[i]);
Max_Heapify(arr, i, 0);
}
}
int majorityElement(vector<int> &nums) {
int n = nums.size();
Heap_Sort(nums);
return nums[n / 2];
}
};
但是效率并不高, 甚至不如STL…(STL的排序还是很能打的)
执行用时：32 ms, 在所有 C++ 提交中击败了12.37%的用户
内存消耗：18.3 MB, 在所有 C++ 提交中击败了46.38%的用户
看来还不是最好的解法.
Partition, 快排思路
这里给出剑指offer中的一种思路, 就是用快排的核心Partition函数,
class Solution {
public:
int majorityElement(vector<int>& nums) {
auto f = [&](int l, int r) { // 每次取pivot=nums[r]的partition
int ll{l - 1};
for (int pivot{nums[r]}, i{l}; i < r; ++i)
if (nums[i] < pivot) swap(nums[++ll], nums[i]);
swap(nums[++ll], nums[r]);
return ll;
};
int n = nums.size(), m = n >> 1, l{}, r{n - 1}, idx{f(l, r)};
while (idx != m)
if (idx > m)
r = idx - 1, idx = f(l, r);
else
l = idx + 1, idx = f(l, r);
return nums[m];
}
};
本质上还是排序+取中点, 但是用了快排的Partition思想, 比直接完全排序要快一些.
双指针($\bigstar$)
后来看到官解评论中有一个思路1, 相当于是简化版的投票算法(官解评论下面全是宝):
每次删除两个不同元素, 众数不会改变.
代码如下:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int lo{}, hi{1}, n = nums.size();
while (hi < n) {
while (hi < n && nums[lo] == nums[hi]) ++hi;
if (hi == n) break;
swap(nums[lo], nums[hi]);
lo += 2, ++hi;
}
return nums[lo];
}
};
真的是精妙, 我就算想到了, 也写不出来…
通过双指针的方法, 有相同元素就后移hi指针, 否则交换左右指针位置的元素, 让左指针右移2, 就相当于删除了两个不同的元素了, 最后左指针指向的就是众数.
然后这个评论下面还有一个思路: (不交换, 直接赋值, 因为前面的元素没用了)
class Solution {
public:
int majorityElement(vector<int>& nums) {
int lo{}, hi{1}, n = nums.size();
while (hi < n) {
while (hi < n && nums[lo] == nums[hi]) ++hi;
if (hi == n) break;
// swap(nums[lo], nums[hi]);
nums[hi] = nums[lo];
lo += 2, ++hi;
}
return nums[lo];
}
};
结果:
执行用时：8 ms, 在所有 C++ 提交中击败了98.51%的用户
内存消耗：18.2 MB, 在所有 C++ 提交中击败了87.62%的用户
精彩!
最后是我看到的一种最简洁的方法2 (思路也是通过抵消完成):
class Solution {
public:
int majorityElement(vector<int> &nums) {
int votes{}, x{};
for (auto num : nums) {
if (votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
};