那些年刷力扣遇到的坑：众数问题
原创那些年刷力扣遇到的坑：众数问题
原创
这道试题出现在《剑指Offer》和LeeCode中，有两种高效的解法：
- 方法一
前提：
存在众数，则中位数一定是众数。
解释：
该方法利用快排中 partition 操作查找中位数，即根据 partition 操作数的 index 判断是否为中位数，循环：若 index == len/2即为中位数，结束循环；index < len/2 时，中位数在 index 右边，将 begin = index+1，继续 partition；index > len/2 时，中位数在 index 左边，将 end = index-1，继续 partition，直到循环结束。根据中位数统计出现次数，判断是否为众数。
Partition实现：
在实现 partition 的时候，有两种思路，一种使用单向指针，一种使用双向指针查找修改，两种思路都是先选出一个操作数 keyNum，遍历数组，将数组分为小于 keyNum 和大于 keyNum 的两部分。
单向指针：
用 small 指针指向小于 keyNum 的索引，初始值为 begin-1；遍历过程中，出现小于 keyNum 的数，small+1后，将其和 small 所指的位置进行交换，当固定了数组中所有小于 keyNum 的数，大于该数的数也就固定了。
双向指针（遇坑）：
错误❌解法：我分别用 begin 和 end 两个指针指向数组首尾，用 begin++ 向后查找大于 keyNum 的数，用 end-- 向前查找小于 keyNum 的数，然后将其交换，当 begin >= end 的时候跳出循环。begin 指向的下一个位置即keyNum 所在位置。而这种方法看似无误，实际上不适合这种问题——在 partition 的过程中，将数组分为两半之后，需要将操作数插入数组中，而 begin 和 end 在执行过程中并没有将 keyNum 的位置留出来。
因此正确解法，应是当我们选出操作数之后，比如 0 位置的数，将其保存下来作为 keyNum。这时 0 位置就可以空出来了，可以用 end-- 向前查找小于 keyNum 的数，与 begin++ 进行交换；然后用 begin++ 向后查找大于等于 keyNum 的数，与 end-- 进行交换， 当begin >= end 的时候跳出循环。此时 begin 所在位置为 keyNum 位置。
示例代码
int majorityElement(vector<int>& nums) {
int len = nums.size();
if(len == 1){
return nums[0];
}
int mid = len >> 1;
int begin = 0, end = len - 1;
// cout<<"mid ="<<mid<<endl;
int index = partition(nums, len, begin, end);
while(index != mid){
if(index > mid){
end = index - 1;
index = partition(nums, len, begin, end);
} else if(index < mid){
begin = index + 1;
index = partition(nums, len, begin, end);
}
}
int result = nums[index];
// if(checkMajorityNumber(nums, len, result)){
// return result;
// }
return result;
}
int partition(vector<int>& nums, int len, int begin, int end){
int key = begin;
int keyNum = nums[key];
while(begin < end){
while(nums[end] >= keyNum && begin < end){
end--;
}
if(begin < end){
nums[begin++] = nums[end];
}
while(nums[begin] < keyNum && begin < end){
begin++;
}
if(begin < end){
nums[end--] = nums[begin];
}
}
swap(keyNum, nums[begin]);
return begin;
}- 方法二（摩尔投票法）
前提：
由于众数出现的次数超过数组长度的一半；若记众数的票数为 +1，非众数的票数为 -1，则一定有所有数字的票数和>0 。
解释：
假设数组 nums 中存在众数为 x，数组长度为 len。若 nums 的前 a 个数字的票数和 =0，则数组后 len-a 个数字的票数和一定仍 >0，即后 len-a 个数字的众数仍为 x。
示例代码
int majorityElement(vector<int>& nums){
if(nums.size() == 0) return -1;
if(nums.size() == 1) return nums[0];
int count = 1;
int keyNum = nums[0];
for(int i = 1; i < nums.size(); i++){
if(count == 0){
keyNum = nums[i];
count = 1;
} else if(nums[i] == keyNum){
count++;
} else{
count--;
}
}
return keyNum;
}测试用例
中位数不存在，中位数存在，数组为空，数组不存在。
参考资料
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
