剑指 Offer 39 数组中出现次数超过一半的数字

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-26 13:15:33
    编辑于：2022-02-26 14:04:17
    浏览量：698

概述

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 上有，代码太乱不想看了。

分治

https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-pvh8/

如果数 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