寻找出现频率超过一半的数-阿里云开发者社区

开发者社区> 人工智能> 正文

寻找出现频率超过一半的数

简介:

以前看到过这个面试题,可惜真面试时忘了。不过知不知道也没区别,因为本来也不知道解法,囧。。

题目:

有一个数组存放int型整数,数字有重复,且有一数字出现的频率超过了50%,请找出这个数字。

分析:

问了下数据量,10000的长度,数字的大小也在10000之内,数据也是乱序的。= =,估计他也没想到我会这么问,随口说的。听了这个数据范围,最先想到的就是排序+扫描,和直接标记法

当然,这肯定不是好的方法,虽然在上述范围内可以解决,其实这个题目可以转化为另一个问题:求这个数组的中位数。至于为什么,想一下就知道。反正我当时没想到。。- -。

排序解法:

首先,对数组进行排序。10000的数据量,快排没问题。然后,直接扫描排序后的数组,找出出现频率超过50%的那个数字。扫描一遍即可。

整个算法复杂度是 O(nlogn)+O(n),完全可以胜任10000的数据量。

一点点优化:

上面说了,其实就是这就是求这个数组的中位数。所以直接输出Array[n/2]即可。这样的话,复杂度就是 O(nlogn)+O(1)。这个优化能让后面的 O(n) 变成 O(1) 。

不过,因为前面的  O(nlogn) 才是大头,所以并不是那么有成效,二者的总体复杂度还是会估计成 O(nlogn)。但无论是简洁程度还是代码量上都好很多。

标记法:

其实,这个也可以认为是一种Hash,只是因为数值小于10000,直接作为下标来Hash就可以了。在Hash的时候,计数一下,超过一半的就是要找的值。这个复杂度是 O(N) 。

如果说,数值很大,那也可用个Hash啊什么的,本质上一样,复杂度也是 O(N) 。其实也可以搞个二叉树嘛,不过复杂度要大一些了,复杂度是 O(nlogn) ,类似快排的复杂度。

以上两种,是我看到这个题目时,最先想到的思路,后面的是我后来查的网上的。

快速选择算法

这个算法和快速排序差不多,复杂度上要好些,最好情况是 O(n) 。其实就是把查找第K个值放到了快排里面,优化了一下。挺不错的算法。

其主要思想就是在快速排序中得到划分结果之后,判断要求的第k个数是在划分结果的左边还是右边,然后只处理对应的那一部分,从而达到降低复杂度的效果。

假设数组为S,先选取一个数作为基准比较数(作者称为“枢纽元”,即pivot),用快排方法把数据分为两部分Sa和Sb。

  • 如果k<= |Sa|( |Sa|表示Sa的大小),则对Sa部分用同样的方法继续操作;
  • 如果k= |Sa| + 1,这个pivot就是第k大值;
  • 如果k> |Sa| + 1,则对Sb部分用同样的方法查找第(k- |Sa|-1)大的值;

与快排不同,快排每次都要对划分后的两部分数据都继续进行同样的快排操作,快速选择不同,只对其中一部分进行操作即可。因为只选择一边进行递归,所以复杂度是 O(n) ,比快排要好,但是两者在最坏情况下的时间复杂度均为 O(n^2) ,出现在每次划分之后左右总有一边为空的情况下。

BFPRT算法

BFPRT算法,又称为中位数的中位数算法,由5位大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan)提出,并以他们的名字命名。参考维基上的介绍Median of medians。这个,我就完全不知道了,最坏情况下 O(n) 复杂度的算法。又看到Floyd,Tarjan的名字了,orz。

算法的思想是修改快速选择算法的主元选取方法,提高算法在最坏情况下的时间复杂度。其主要步骤为:

  1. 首先把数组按5个数为一组进行分组,最后不足5个的忽略。对每组数进行排序(如插入排序)求取其中位数。
  2. 把上一步的所有中位数移到数组的前面,对这些中位数递归调用BFPRT算法求得他们的中位数。
  3. 将上一步得到的中位数作为划分的主元进行整个数组的划分。
  4. 判断第k个数在划分结果的左边、右边还是恰好是划分结果本身,前两者递归处理,后者直接返回答案。

首先看算法的主程序,代码如下。小于5个数的情况直接处理返回答案。否则每5个进行求取中位数并放到数组前面,递归调用自身求取中位数的中位数,然后用中位数作为主元进行划分。

总结:

总的来说,算法复杂度可以达到 O(n) ,如果使用快速选择算法,耍贱点就是Hash算法(略大的空间复杂度)。挫一点的话就是快排,复杂度也在 O(nlogn),足以抗100万级别的数据量了一般比赛的时候基本能混过去(b_d),除非遭遇变态强的数据。最后那个神算法真不知道。

回过头看这些算法,除了Hash外,别的算法基本都和快排有着关联,真是佩服快排的发明者。

转载请注明:旅途@KryptosX » 寻找出现频率超过一半的数

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章