A zero-indexed array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.
For example, consider array A such that
A[0] = 3 A[1] = 4 A[2] = 3
A[3] = 2 A[4] = 3 A[5] = -1
A[6] = 3 A[7] = 3
The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.
Write a function
class Solution { public int dominator(int[] A); }
that, given a zero-indexed array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.
Assume that:
- N is an integer within the range [0..1,000,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
For example, given array A such that
A[0] = 3 A[1] = 4 A[2] = 3
A[3] = 2 A[4] = 3 A[5] = -1
A[6] = 3 A[7] = 3
the function may return 0, 2, 4, 6 or 7, as explained above.
Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
解决方案:
时间复杂度和空间复杂度都能满足
public int dominator(int[] A) {
int n = A.length;
Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
for(int i = 0; i < n; i++) {
int a = A[i];
if(hash.containsKey(a)) {
hash.put(a, (hash.get(a) + 1));
} else {
hash.put(a, 1);
}
if(hash.get(a) * 2 > n) {
return i;
}
}
return -1;
}
分享到:
相关推荐
图像检测算法2图像检测算法2图像检测算法2图像检测算法2图像检测算法2图像检测算法2图像检测算法2图像检测算法2图像检测算法2图像检测算法2图像检测算法2图像检测算法2
最全最清晰的国密算法SM2、SM3、SM4算法标准规范。 SM1 为对称加密。其加密强度与AES相当。该算法不公开,调用该算法时,需要通过加密芯片的接口进行调用。 SM2为非对称加密,基于ECC。该算法已公开。由于该算法基于...
磁盘调度算法包括: 1.先来先服务算法 2.电梯(扫描)算法 3复制请求队列 4.最短路径优先算法
国密算法 SM2_SM3_SM4 C语言实现
C#国密加密算法SM2,SM3,SM4的一个实现案例,不涉及具体的算法剖析,在网络上关于这个加密算法的文档较少,切在跨语言加密解密上会存在一些问题,所以整理。
国密算法SM2,SM3,SM4的技术规范,官方文档.描述详细
算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法
2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的...
国密算法功能 1. SM2 加密解密、公钥私钥生成、签名与验签; 2. SM4 加密解密; 3. SM3加密 4. 代码实现、调用案例源码 代码经过本人测试通过,调用BouncyCastle.Crypto.dll的全部实现代码,源码分享。
漫画算法系列-2020.11.25(B).pdf
1.1 进化类算法 2 1.2 群智能算法 3 1.3 模拟退火算法 5 1.4 禁忌搜索算法 5 1.5 神经网络算法 6 参考文献 6 第2章 遗传算法 9 2.1 引言 9 2.2 遗传算法理论 10 2.2.1 遗传算法的生物学基础 10 ...
“第2篇算法基本应用篇”详细讲解了算法在排序、查找、数值计算、数论、经典趣题和游戏中的应用;“第3篇算法高级应用篇”讲解了算法的一些高级应用技术,包括在密码学和数据压缩/解压缩中的应用。 《C/C++常用算法...
SM3withSM2数字签名算法的实现 SHA1WithSM2数字签名算法的实现 SHA256WithSM2数字签名算法的实现 SM3withRSA数字签名算法的实现 密钥协商功能 国密SM2 ECDHE密钥协商算法的实现 摘要算法 SM3摘要算法的实现 X509...
贝叶斯网络学习算法――k2算法,对于学习数据挖掘的人有用的,涉及到了分类预测算法
2. 掌握以上算法生成直线段的基本过程; 3. 通过编程,会在C/C++环境下完成用DDA算法、中点bresenham算法及bresenham算法对任意直线段的扫描转换。 实验设备及实验环境 计算机(每人一台) VC++6.0或其他C/C++语言...
排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc排序算法2.doc
动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法.
算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法
LFU算法LFU算法LFU算法LFU算法LFU算法
基于c++语言的聚类算法实现,1.k-means聚类算法 2.层次聚类算法 3.SOM聚类算法 4.FCM聚类算法