剑指 Offer 39 数组中出现次数超过一半的数字
概述
https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
https://leetcode.com/problems/majority-element/
题目希望线性时间复杂度和常量空间复杂度。
暴力法
遍历所有，计数。
但是我们就变成了线性时间复杂度。
O(n) 求中位数
显然暴力法没有利用目标元素出现次数大于一半的特性。
常量空间复杂度一般可以通过在输入数组上做记录来解决，但是这里的 n 的范围是整个 INT 类型的取值范围欸。
如果能把，每个数字的值都集中起来的话，数组中间的值必然是目标值。
我们有成熟的时间复杂度为 O(n) 的算法得到数组中任意第 k 大的数字。
不想看了，剑指 Offer 上有，代码太乱不想看了。
分治
如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
所以将数组一分为二，分别求出两部分的众数，然后再从这两个之间选出正确的一个，选择方法就是遍历一遍并计数。
时间复杂度：O(nlogn)。 空间复杂度：O(logn)，用的栈空间，进行了 O(logn) 次递归。
class Solution {
public:
int majorityElement(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
int helper(vector<int>& nums, int l, int r) {
if (l == r) return nums[l];
int m = (r - l) / 2 + l;
int a = helper(nums, l, m);
int b = helper(nums, m + 1, r);
if (rangeCount(nums, l, r, a) > rangeCount(nums, l, r, b)) {
return a;
} else {
return b;
}
}
int rangeCount(vector<int>& nums, int l, int r, int t) {
int count = 0;
for (int i = l; i <= r; i ++) {
if (nums[i] == t) count ++;
}
return count;
}
};
Boyer-Moore 投票算法
我们遍历数组，如果下一个字符与当前字符相同，次数加一，不同则减一，如果减到零则更换为新字符。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int num = nums[0];
int times = 1;
for (int i = 1; i < nums.size(); i ++) {
if (times == 0) {
times = 1;
num = nums[i];
continue;
}
if (nums[i] == num) {
times ++;
} else {
times --;
}
}
return num;
}
};
Links: sword-offer-39