剑指 Offer 39. 数组中出现次数超过一半的数字
题目链接： 剑指 Offer 39. 数组中出现次数超过一半的数字
有关题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
题解
法一：分治
参考官方题解
class Solution {
int countInRange(vector<int>& nums, int target, int l, int r)
{
int cnt = 0;
for (int i = l; i <= r; i++)
{
if (nums[i] == target)
cnt++;
}
return cnt;
}
int majorityElementRec(vector<int>& nums, int l, int r)
{
if (l == r)
return nums[l];//递归结束条件
//分治,拆分乘两个区间,可以证明我们只需，求得两个区间中的众数即可
//再递归进行继续拆分子区间，求得子区间的众数
//当子区间为长度为 1 时，子区间的众数为该子区间的唯一数
int mid = (r - l) / 2 + l;
int left = majorityElementRec(nums, l, mid);
int right = majorityElementRec(nums, mid + 1, r);
if (left == right)//众数相同，直接返回即可
return left;
if (countInRange(nums, left, l, r) > (r - l + 1) / 2)
return left;
if (countInRange(nums, right, l, r) > (r - l + 1) / 2)
return right;
return -1;
}
public:
int majorityElement(vector<int>& nums) {
return majorityElementRec(nums, 0, nums.size() - 1);
}
};