现在有一个数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数。
答案1:
创建一个hash_map,key为数组中的数,value为此数出现的次数。遍历一遍数组,用hash_map统计每个数出现的次数,并用两个值存储目前出现次数最多的数和对应出现的次数。
这样可以做到O(n)的时间复杂度和O(n)的空间复杂度,满足题目的要求。
但是没有利用“一个数出现的次数超过了一半”这个特点。也许算法还有提高的空间。
答案2:
使用两个变量A和B,其中A存储某个数组中的数,B用来计数。开始时将B初始化为0。
遍历数组,如果B=0,则令A等于当前数,令B等于1;如果当前数与A相同,则B=B+1;如果当前数与A不同,则令B=B-1。遍历结束时,A中的数就是要找的数。
这个算法的时间复杂度是O(n),空间复杂度为O(1)。
这道题也可以这么解,先两两比较,如果相同则留下,如果不同则两个都删除,则一遍之后,那个多于一半的数在剩下的里面还是多于一半,然后再重复上述过程,直到最后
由于出现过半,所求数肯定是出现次数最多的数,即转化为“求出现次数最多的数”,利用hashmap, O(N)时间内可以求得。
int max;
int dat;
Hashmap map;
for each num
if(map.has(num)) {
int cnt = map.get(num);
map.set(num, cnt+1);
if(cnt + 1 > max) { max = cnt+1; dat = num; }
}
else map.put(num, 1);
//for each
>the data you want is dat that appears max times.
分享到:
相关推荐
分治算法求n个数的数组中找出第二个最大元素
已知不相同的数不超过10000个,现在需要在其中查找某个自然数,如找到则输出并统计这个自然数出现的次数,如没找到则输出NO。 Input 输入由多组测试数据组成。 每组测试数据输入包含n+1行; 第一行是两个整数n...
一种O_n_nlog_2m_时间复杂度的排序算法.pdf
用递归算法编写求一个数组A中的最大元素;/****一个递归算法,求数组A中最大的元素***/ #include int Max(int A[], int i, int j) //求顺序表A中的最大元素 ……
已知一个int数组, 编程从数组中获取最大数,初学者,不知道是否正确。
C语言程序设计-有一个一维数组score,内放10个学生的成绩,用一个函数来求平均成绩;
//已知数组a[n]、b[n],设计一算法给数组b[n]赋值,且 //b[i]=a[0]*a[1]*……*a[n-2]*a[n-1]/a[i],要求如下: //1.算法不能包含除法 //2.算法时间复杂度为o(n) //3.空间复杂度为o(1)(除循环技术变量外没有其他变量)
数组a中已存有互不相同的10个整数从键盘输入一个整数,找出与该值相同的数组元素下标。 (如果没找到,输出“没找到”).c
现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。 此题请勿采用将序列X和Y合并找第k小的O(m+n)的一般方法,要充分利用X和Y已经排好序的这一特性。 输入格式 第一行有三个数,...
已知(k1, k2, …, kp)是堆,则可以写一个时间复杂度为O(logn)的算法,将(k1, k2, …, kp, kp+1)调整为堆。试编写“从p=1起,逐个插入建堆”的算法,并讨论由此方法建堆的时间复杂度。
分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
(1) 根据下述情况,分别编写程序,记录 BX 中 1 的个数(需要考虑 BX 中二进制 串的特殊情况),要求如下: ...和为目标值,请设计一个算法,将时间复杂度控制在 O(n),编程实现并验证 你的算法。
统计一个长整型数字中0-9分别出现的次数java 7count number.rar
例5.1 输入n个数,要求程序按输入时的逆序把这n个数打印出来,已知整数不超过100个。也就是说,按输入相反顺序打印这n个数。 例5.2 将a数组中第一个元素移到数组末尾,其余数据依次往前平移一个位置。 例5.3 一维...
力扣热题Python源代码 题目153....你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1: 输入:nums = [3,4,5,1,2] 输出:1 解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
5.15 数据段中已定义了一个有N个字数据的数组M,试编写一程序求出M中绝对值最大的数,把它放在数据段的M+2n单元中,并将该数的偏移地址存放在M+2(n+1)单元中。 5.16 在首地址为DATA的字数组中,存放了100H个16位...
n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法...
可以方便的计算信号或时间序列的复杂度,用于信号处理,特征提取等方面
如果直接用python的一个list除以一个数,会报错: a = [1.0, 1.0, 1.0] c = a/3 print(c) TypeError: unsupported operand type(s) for /: ‘list’ and ‘int’ 使用Numpy可以轻松做到: import numpy as np a = ...
这种类型的对象可以存储10个20~80之间的整数,即他的内部有一个整型数组存储数据。编程: (1) 判断两个inergerSet类对象S1和S2是否相等。提示:集合相等的前提是所有元素相等。 (2) 输出两个集合对象的交集。 ...