出现次数超过一半(50%)的数

【题目要求】给你n个数与n。现在需要你在O(n)的时间内，O(1)的空间内找出出现次数超过50%的数。

【开始胡扯】一开始我看到这道题瞬间蒙蔽(ToT)/~~~(。﹏。*)，要是只有O(n)的时间这一条要求，就可以用哈希瞬间解决（也就是用空间换时间），对于O(1)的空间好像很难解决。

【思路一】双重循环，这是解决这道题效率最低的方法了，也就是对每个数都计算它出现的次数，时间复杂度 O(n^2) 直接Out。

【思路二】先排序，让相近的数字排在一起，然后从第一个数开始遍历，现在给一个例子，如：1000012，现在进行排序：0000112，从0开始，设定一个计数器T=0，现在有4个0，则T=4，发现超过了半数，输出0。这个方法就是上一个方法的优化版，Out。

【思路三】就是以空间换时间，哈希的思想，使一个一维数组有两个含义。比如a[x]=y代表x这个数出现了y次，这个方法时间复杂度是O(n)，但是空间实在是……不说了(* ￣︿￣) Out

【思路四】先算出概率，选出这些数中最有可能符合要求的几个数，再随机抽取几个。这……还是算了吧。

【思路五】今天的主题，就是所谓的MJRTY算法，也叫多数投票算法，主要思路如下:（这个算法时间复杂度O(n)！空间上不需要额外的储存，所以空间复杂度是O(1)!!!!!!）

如果count==0，则将vote的值设置为数组的当前元素，将count赋值为1；

否则，如果vote和现在数组元素值相同，则count++，反之count–；

重复上述两步，直到扫描完数组。

count赋值为0，再次从头扫描数组，如果数组元素值与vote的值相同则count++，直到扫描完数组为止。

如果此时count的值大于等于n/2，则返回vote的值，反之则返回-1；

以下是代码实现，由于题目保证结果一定存在，所以我们省去了最后一步的检查验证。

关键代码如下所示：

#include<iostream>
using namespace std;
int len;
void Find(int* a, int N)
{
char candidate;
int nTimes, i;
for(i=nTimes=0;i<N;i++)
{
if(nTimes==0) candidate=a[i],nTimes=1;
else
{
if(candidate==a[i]) nTimes++;
else nTimes--;
}
}
cout<<candidate;
}
int main()
{
cin>>len;
int a[len];
for(int i=0;i<n;i++) cin>>a[i];
Find(a,len);
system("pause");
return 0;
}

以上所述是小编给大家介绍的出现次数超过一半(50%)的数，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • java统计字符串中指定元素出现次数方法

    java统计字符串中指定元素出现次数方法

    本文实例讲解了统计文本中某个字符串出现的次数或字符串中指定元素出现的次数方法,分享给大家供大家参考,具体内容如下 运行效果图: 程序查找的上此文件带"a"的字符在多少次 具体代码如下 package com.zuidaima.util.string; import java.io.*; public class CountString { public static int count(String filename, String target) throws FileNotFoun

  • C++求1到n中1出现的次数以及数的二进制表示中1的个数

    在从 1 到 n 的正数中 1 出现的次数 题目: 输入一个整数 n,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数. 例如输入 12,从 1 到 12 这些整数中包含 1  的数字有 1, 10, 1 1 和 12, 1 一共出现了 5 次 代码实现(GCC编译通过): #include "stdio.h" #include "stdlib.h" int count1(int n); int count2(int n); int main(void

  • 基于Java代码实现数字在数组中出现次数超过一半

    下文通过几种方法给大家介绍java数组数字出现次数,具体内容如下所示: 方法一: 数组排序,然后中间值肯定是要查找的值. 排序最小的时间复杂度(快速排序)O(NlogN),加上遍历. 方法二: 使用散列表的方式,也就是统计每个数组出现的次数,输出出现次数大于数组长度的数字. 方法三: 出现的次数超过数组长度的一半,表明这个数字出现的次数比其他数出现的次数的总和还多. 考虑每次删除两个不同的数,那么在剩下的数中,出现的次数仍然超过总数的一般,不断重复该过程,排除掉其他的数,最终找到那个出现次数超过

  • Java用Cookie限制点赞次数(简版)

    本文简单利用Cookie技术来简单的限制点赞次数,并不能杜绝游客的恶意点赞. 好了,不啰嗦了,先来看看基础知识: ajax+springMVC+cookie 中间框架你随意,楼主这里用了springMVC,只要取得HttpServletRequest和HttpServletResponse你就可以操作cookie啦 什么是Cookie cookie 是存储于访问者的计算机中的变量.每当同一台计算机通过浏览器请求某个页面时,就会发送这个 cookie.你可以使用 JavaScript 来创建和取回

  • JS+JSP通过img标签调用实现静态页面访问次数统计的方法

    本文实例讲述了JS+JSP通过img标签调用实现静态页面访问次数统计的方法.分享给大家供大家参考,具体如下: 测试页面: test.html <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <title>test</title> <meta http-equiv="pragma" content

  • 出现次数超过一半(50%)的数

    [题目要求]给你n个数与n.现在需要你在O(n)的时间内,O(1)的空间内找出出现次数超过50%的数. [开始胡扯]一开始我看到这道题瞬间蒙蔽(ToT)/~~~(.﹏.*),要是只有O(n)的时间这一条要求,就可以用哈希瞬间解决(也就是用空间换时间),对于O(1)的空间好像很难解决. [思路一]双重循环,这是解决这道题效率最低的方法了,也就是对每个数都计算它出现的次数,时间复杂度 O(n^2) 直接Out. [思路二]先排序,让相近的数字排在一起,然后从第一个数开始遍历,现在给一个例子,如:10

  • php实现数组中出现次数超过一半的数字的统计方法

    数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字.例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}.由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2.如果不存在则输出0. 两种方式: 1.定义一个新数组arr,遍历数组给arr赋值,arr[元素]=出现的次数 2.排序下arr,取第一个的key和value,key是目标元素,value是出现次数,验证下后返回 3.时间复杂度是O(n) 空间上会新创建个数组 1.定义变量e代表出现次数最多的元素,变量coun

  • java求数组元素重复次数和java字符串比较大小示例

    复制代码 代码如下: /** * Name: 求数组中元素重复次数对多的数和重复次数 * Description:  * 数组中的元素可能会重复,这个方法可以找出重复次数最多的数,同时可以返回重复了多少次. * 但需要知道这个数组中最大的元素是多少,如果无法确定,就悲剧啦~ * * @param array目标数组: *           max数组中数据的最大值: * @return 返回一个包含重复次数最多的数(value)和重复次数(maxCount)的map集合: *         

  • C语言编写猜数游戏

    C语言编写猜数游戏

    C语言写猜数游戏,供大家参考,具体内容如下 这篇文章是给学完并学懂了C语言的分支(选择和循环)结构的朋友看的. 要做一个游戏或者程序先要想好有那些要求,以下是我认为一个猜数游戏必带的要求: 1.自定义猜数范围的起点和终点以及机会次数. 2.生成一个随机数. 3.如果输入猜入的数和生成的随机数相等,就提示猜对了并退出主函数,如果输入猜的数比生成的随机数大,就提示猜大了,如果输入猜的数比生成的随机数小,就提示猜小了,没猜对一次就减一次机会. 4.如果机会为0了,就提示没有机会了并输出随机数. 自定义

  • php数组的一些常见操作汇总

    数组求和 给定一个含有n个元素的整型数组a,求a中所有元素的和.可能您会觉得很简单,是的,的确简单,但是为什么还要说呢,原因有二,第一,这道题要求用递归法,只用一行代码.第二,这是我人生中第一次面试时候遇到的题,意义特殊. 简单说一下,两种情况: 如果数组元素个数为0,那么和为0. 如果数组元素个数为n,那么先求出前n - 1个元素之和,再加上a[n - 1]即可. 复制代码 代码如下: // 数组求和 int sum(int *a, int n) { return n == 0 ? 0 : s

  • Apache的压力测试以及web性能优化的常用知识总结

    什么是带宽? 误解:"数据在线路中的移动速度"."数据的传输速度" 我们所说的带宽是指数据的发送速度,比如百兆网卡,指网卡的最大发送速度是100Mbps,也就是说网卡在一秒钟最多可以发送100Mb的数据:相关的因素: 数据发送装置将二进制信号传送到线路的能力,也称信号传输频率,以及另一端数据接收装置对二进制信号接收的能力,也包括线路对传输频率的支持程度: 数据传输介质的并行度,等价于计算机系统总线宽度的概念: 习惯与约定 b:比特单位 bit: B:字节单位 Byt

  • 使用Apache ab工具对Apache服务器进行简单的压力测试

    1.安裝ab命令 sudo apt-get install apache2-utils 2.ab命令参数说明 Usage: ab [options] [http[s]://]hostname[:port]/path  Options are: //总的请求数 -n requests Number of requests to perform //一次同时并发的请求数 总的请求数(n)=次数*一次并发数(c) -c concurrency Number of multiple requests t

  • Android自定义View实现水面上涨效果

    Android自定义View实现水面上涨效果

    实现效果如下: 实现思路: 1.如何实现圆中水面上涨效果:利用Paint的setXfermode属性为PorterDuff.Mode.SRC_IN画出进度所在的矩形与圆的交集实现 2.如何水波纹效果:利用贝塞尔曲线,动态改变波峰值,实现"随着进度的增加,水波纹逐渐变小的效果" 话不多说,看代码. 首先是自定义属性值,有哪些可自定义属性值呢? 圆的背景颜色:circle_color,进度的颜色:progress_color,进度显示文字的颜色:text_color,进度文字的大小:tex

  • 用tensorflow搭建CNN的方法

    用tensorflow搭建CNN的方法

    CNN(Convolutional Neural Networks) 卷积神经网络简单讲就是把一个图片的数据传递给CNN,原涂层是由RGB组成,然后CNN把它的厚度加厚,长宽变小,每做一层都这样被拉长,最后形成一个分类器 在 CNN 中有几个重要的概念: stride padding pooling stride,就是每跨多少步抽取信息.每一块抽取一部分信息,长宽就缩减,但是厚度增加.抽取的各个小块儿,再把它们合并起来,就变成一个压缩后的立方体. padding,抽取的方式有两种,一种是抽取后的

随机推荐