主要元素


题目

数组中占比超过一半的元素称之为主要元素。给定一个整数数组,找到它的主要元素。若没有,返回-1。

示例 1:

输入:[1,2,5,9,5,9,5,5,5]
输出:5

示例 2:

输入:[3,2]
输出:-1

示例 3:

输入:[2,2,1,1,1,2,2]
输出:2

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-majority-element-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

分析

那道题的第一反映, 是通过 map 来做, 统计数组中各个数字出现的次数,然后找到最大的。

这样的解法并无不妥,只是这世上大多有那样一群人,能够想出很多有趣而高效的解法,比如 摩尔投票法

摩尔投票法的前提,是默认存在这样的一个数,它超过占比的一半。

基于此前提,我们依次取出元素,用 count 来记录取出元素出现的次数, 用 major 来记录主要元素

再取出之后的一个元素,相同则 count + 1 , 否则则 count - 1 。但 count = 0 时, 更新major 为下一个值。

因为 major主要元素,意味着,它可以将所有其他元素消灭后,还能留下自己。

而该算法的核心也就是消灭元素。

作者:喝七喜
链接:https://www.zhihu.com/question/49973163/answer/235921864
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

我们再根据只有两个变量的实际代码理一遍:

major 初始化随便一个数,

count 初始化为0

输入:{1,2,1,3,1,1,2,1,5}

  • 扫描到1,count是0(没有元素可以和当前的1抵消),于是major = 1,count = 1(此时有1个1无法被抵消)
  • 扫描到2,它不等于major,于是可以抵消掉一个major => count -= 1,此时count = 0,其实可以理解为扫到的元素都抵消完了,这里可以暂时不改变major的值
  • 扫描到1,它等于major,于是count += 1 => count = 1
  • 扫描到3,它不等于major,可以抵消一个major => count -= 1 => count = 0,此时又抵消完了(实际的直觉告诉我们,扫描完前四个数,1和2抵消了,1和3抵消了)
  • 扫描到1,它等于major,于是count += 1 => count = 1
  • 扫描到1,他等于major,无法抵消 => count += 1 => count = 2 (扫描完前六个数,剩两个1无法抵消)
  • 扫描到2,它不等于major,可以抵消一个major => count -= 1 => count = 1,此时还剩1个1没有被抵消
  • 扫描到1,它等于major,无法抵消 => count += 1 => count = 2
  • 扫描到5,它不等于major,可以抵消一个major => count -= 1 => count = 1

至此扫描完成,还剩1个1没有被抵消掉,它就是我们要找的数。

代码

class Solution {
    public int majorityElement(int[] nums) {
       int major = -1;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                major = num;
            }
            count += (major == num) ? 1 :-1;
        }

        int moreThanHalf = nums.length / 2;
        count = 0;
        for (int num : nums) {
            if (num == major) {
                count++;
            }
            // if (count > moreThanHalf) {
            //     return major;
            // }
        }

        return count > moreThanHalf ? major : -1;

        // return -1;
    }
}

扩展

如何通过摩尔投票法,求取超过 1/3 的元素?

作者:facetothefate
链接:https://www.zhihu.com/question/284969980/answer/440979325
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

摩尔投票法基于这样一个定理:

如果一个数组里存在一个数超过一半,那么同时删去两个不同的数,超过一半的数仍然超过一半。

证明:

如果删去的两个数都不是抄过一半的,那么显然超过一半的还是超过一半。

如果删去的两个数有一个是超过一半的:由于超过一半的数>n/2,假如我每次都删除一个超过一半的,一个不超过一半的,那么一定是不超过一半的数先被删完。

证明完毕。

好了,那么找到超过一半的数,就是扫描数组,每次都删去两个不同的数,最后没有不同的了,剩下的就是超过一半的数。

好了,那么我们推广一下这个定理,看看怎么适用在任意情况下,也就是我们可以找到占任意比例的元素。

比如,寻找1/3的元素。

定理:如果一个数组里有一元素超过1/3,那么同时删除3个不同的数,超过1/3的数扔超过1/3

证明:

如果删除的3个数都不是超过1/3的元素,那么显然成立。

如果删除的3个数有一个是超过1/3的元素,设该元素有 [公式]

即证明:

[公式]

[公式]

[公式]

[公式]

[公式]

证明完毕

推广到k:

如果一个数组里有一元素超过1/k, 那么同时删除k个不同的数,超过1/k的数仍然超过1/k

如果删除的k个数都不是超过1/k的元素,那么显然成立

如果删除的k个数有一个是超过1/k的元素,设该元素有 [公式]

即证明:

[公式]

[公式]

[公式]

[公式]

[公式]

证明完毕


文章作者: peifeng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 peifeng !
 上一篇
每日事毕 每日事毕
每日事毕前几日, 与老友前往宝石山爬山。约在了早上九点。 已然约摸 30 岁的年纪,但仍旧孑然一身,有时不免有些惭愧,但不在此时。 大概七点多,我起来洗漱完,就开始导航如何到达目的地。首选必然是地铁,只是看到地铁需要约 90 分钟,当时不知
2020-10-16
下一篇 
转置矩阵 转置矩阵
题目 转置矩阵 给定一个矩阵 A, 返回 A 的转置矩阵。 矩阵的转置是指将矩阵的主对角线翻转,交换矩阵的行索引与列索引。 示例 1: 输入:[[1,2,3],[4,5,6],[7,8,9]]输出:[[1,4,7],[2,5,8],[3,6
2020-10-14
  目录