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;
}
分享到:
相关推荐
最全最清晰的国密算法SM2、SM3、SM4算法标准规范。 SM1 为对称加密。其加密强度与AES相当。该算法不公开,调用该算法时,需要通过加密芯片的接口进行调用。 SM2为非对称加密,基于ECC。该算法已公开。由于该算法基于...
js国密算法sm2以及国密算法sm3 js的实现以及例子 js国密算法sm2以及国密算法sm3 js的实现以及例子
经典算法2(素数算法).c
主要在于介绍统计迭代重建算法研究与优化,便于理解与运用
国密算法功能 1. SM2 加密解密、公钥私钥生成、签名与验签; 2. SM4 加密解密; 3. SM3加密 4. 代码实现、调用案例源码 代码经过本人测试通过,调用BouncyCastle.Crypto.dll的全部实现代码,源码分享。
简单的clock页面置换算法 采用CLOCK置换算法仿真请求分页系统 1、设计目的:用高级语言编写和调试一个内存分配程序,加深对内存分配算法的理解。 2、设计要求: 1) 实现请求分页存储管理方式的页面置换算法:...
2.内容:基于matlab的Dalin大林控制算法仿真 +代码操作视频 3.用处:用于Dalin大林控制算法编程学习 4.指向人群:本硕博等教研学习使用 5.运行注意事项: 使用matlab2021a或者更高版本测试,运行里面的Runme_.m...
使用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...
2. **SM3算法**:SM3是一种密码散列函数,类似于SHA-256,用于产生固定长度的摘要值。在Java中,你可以通过扩展`MessageDigest`类或者使用特定库来实现SM3哈希计算,以确保数据的完整性和一致性。 3. **SM4算法**:...
改进MFO算法火焰更新方式,加快其收敛速度
2. **分治算法**:分治策略是将一个大问题分解为两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。典型的分治算法包括快速排序、归并排序和大数乘法等。 3. **...
SM3withSM2数字签名算法的实现 SHA1WithSM2数字签名算法的实现 SHA256WithSM2数字签名算法的实现 SM3withRSA数字签名算法的实现 密钥协商功能 国密SM2 ECDHE密钥协商算法的实现 摘要算法 SM3摘要算法的实现 X509...
国密算法sm2算法c语言实现,vc++环境,
sm2算法sm2算法sm2算法sm2算法
纵横交叉算法纵横交叉算法新型的群智能算法 纵横交叉算法纵横交叉算法新型的群智能算法 纵横交叉算法纵横交叉算法新型的群智能算法 纵横交叉算法纵横交叉算法新型的群智能算法 纵横交叉算法纵横交叉算法新型的群智能...
2. 搜索算法:二分查找、线性查找、深度优先搜索(DFS)和广度优先搜索(BFS)是常见的搜索方法,用于在数据结构中找到特定元素。 3. 递归:递归是一种函数自我调用的技术,用于解决复杂问题,如斐波那契数列和汉诺...
2、基本遗传算法 3、遗传算法的特点 二、遗传算法原理 1、遗传算法的数学基础 2、遗传算法的收敛性分析 3、遗传算法的改进 三、遗传算法的应用 (1)组合优化 (2)函数优化 (3)自动控制 (4)生产调度 (5...
粒子群算法(Particle Swarm Optimization, PSO)与遗传算法(Genetic Algorithm, GA)是两种在优化问题中广泛应用的全局搜索方法。它们都是基于自然选择和群体智能的启发式算法,能够有效地解决复杂多模态优化问题...