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:小灰的算法进阶》是一本以漫画形式生动展现算法进阶知识的图书。本书以小灰的视角,通过一系列有趣的场景和生动的漫画,深入浅出地讲解了算法的高级概念和技术,包括图算法...
K2算法是其中一种用于学习贝叶斯网络结构的算法,尤其适用于小到中等规模的数据集。 K2算法,全称为Cowell-Koller-Komorowski算法,由R. Cowell、M. Koller、A. Komorowski于1994年提出。该算法基于最大后验概率...
js国密算法sm2以及国密算法sm3 js的实现以及例子 js国密算法sm2以及国密算法sm3 js的实现以及例子
国密算法 SM2_SM3_SM4 C语言实现
C#国密加密算法SM2,SM3,SM4的一个实现案例,不涉及具体的算法剖析,在网络上关于这个加密算法的文档较少,切在跨语言加密解密上会存在一些问题,所以整理。
经典算法2(素数算法).c
[新版]最佳适应算法_最坏适应算法2.doc
主要在于介绍统计迭代重建算法研究与优化,便于理解与运用
国密算法功能 1. SM2 加密解密、公钥私钥生成、签名与验签; 2. SM4 加密解密; 3. SM3加密 4. 代码实现、调用案例源码 代码经过本人测试通过,调用BouncyCastle.Crypto.dll的全部实现代码,源码分享。
磁盘移臂调度算法作业 1、实验目的:加深对于操作系统设备管理技术的...(2)能对两种算法给定任意序列不同的磁盘请求序列,显示响应磁盘 请求的过程。 (3)能统计和报告不同算法情况下响应请求的顺序、移臂的总量。
2. 基于贪心策略的超启发式算法 3. 基于元启发式算法的超启发式算法 4. 基于学习的超启发式算法 基于随机选择的超启发式算法 基于随机选择的超启发式算法是从给定的集合中随机选择 LLH,组合形成新的启发式算法。...
使用python实现了可视域计算的几种经典算法,包括LOS算法,Xdraw算法,参考面算法等
10.s8算法2-4 链表 哈希表 11.s8算法2-5 算法题 12.S8设计模式-1 设计模式简介 13.S8设计模式-2 创建型模式 14.S8设计模式-3 结构型模式 15.S8设计模式-4 行为型模式 16.5 设计模式总结 17.6 二叉树 18.7 算法进阶 2...
它属于SHA-2(安全哈希算法2)家族,由美国国家安全局(NSA)设计,并在2001年由美国国家标准与技术研究所(NIST)发布。SHA256算法能够将任意长度的数据转化为一个固定长度的输出,即256位的哈希值,通常以16进制...
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++常用算法...
2. **分治算法**:分治策略是将一个大问题分解为两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。典型的分治算法包括快速排序、归并排序和大数乘法等。 3. **...
SM3withSM2数字签名算法的实现 SHA1WithSM2数字签名算法的实现 SHA256WithSM2数字签名算法的实现 SM3withRSA数字签名算法的实现 密钥协商功能 国密SM2 ECDHE密钥协商算法的实现 摘要算法 SM3摘要算法的实现 X509...