一个含N个整数的数组,其中一个元素出现次数 k>N/2,找出这个元素。限O(N)时间,O(1)空间。其实就是找数组中出现次数最多的那个元素,看到一篇帖子,调试了一把发现有问题,
http://hi.baidu.com/wzfxyer/blog/item/a16bec99e6b7700f6f068c69.html
public class FindKinN {
public static void main(String[] args) {
int[] a = {1,1,1,1,2,2,1,1,2,2,2,1};
int count,cur,n;
count = 0;
cur = 0;
n = a.length;
for (int i = 0; i < n; i++)
{
if (count == 0) cur = a[i];
if (cur == a[i])
count++;
else
count--;
}
System.out.println("你要找的是:" + cur);
}
}
//适用范围:必须有支配者,而且必须大于n/2。
调试了一把,发现算法有问题,修改如下:
public class FindKinN {
public static void main(String[] args) {
int[] a = { 4, 3, -1, 3, 4, 3, 5 };
int count, cur, n;
count = 0;
cur = a[0];
n = a.length;
for (int i = 0; i < n; i++) {
if (cur == a[i])
count++;
else {
count--;
if (count == 0){
cur = a[i];
}
}
}
System.out.println("你要找的是:" + cur);
}
}
到底对不对心里没有底,请高手帮忙分析一下。
我也感觉不对,因为我想在count--之后才能变成0,故可能前面不用判断了,我再加上,再看看有什么问题。
public class FindKinN {
public static void main(String[] args) {
int[] a = {4,3,-1,3,4,3,5,4,4,4,4,4,4};
int count, cur, n;
count = 0;
cur = a[0];
n = a.length;
for (int i = 0; i < n; i++) {
if (count == 0){
cur = a[i];
}
if (cur == a[i])
count++;
else {
count--;
if (count == 0){
cur = a[i];
}
}
}
System.out.println("你要找的是:" + cur);
}
}
我实现了一个很笨的算法,无论是时间复杂度还是空间复杂度都超了,希望谁给我改正一下:
import java.util.HashMap;
import java.util.Map;
public class FindKinN {
public static void main(String[] args) {
int[] array = {3,4,3,2,-1,3,3};
System.out.println(search(array));
}
public static int search(int[] array){
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i =0; i < array.length; i++){
Integer value = map.get(array[i]);
if(value == null){
map.put(array[i], 1);
} else {
map.put(array[i], value + 1);
}
}
int maxValue = -1;
int maxKey = -1;
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
int nextValue = entry.getValue();
if(nextValue > maxValue){
maxValue = nextValue;
maxKey = entry.getKey();
}
}
return maxKey;
}
}
分享到:
相关推荐
SSA算法下的麻雀算法随机森林二分类与多分类预测建模(Matlab程序)图形展示与数据优化图分析,麻雀算法SSA优化随机森林做二分类和多分类预测建模。 程序内注释详细直接替数据就可以使用。 程序语言为matlab。 程序...
《算法导论》是一本深度探讨计算机算法的权威著作,对于理解、设计和分析算法具有极其重要的指导价值。这本书深入浅出地介绍了各种基础和高级算法,是许多计算机科学专业学生以及软件工程师的重要参考书。中文版的...
在旅行商问题(TSP)中,遗传算法被用来寻找一条最短路径,使得旅行商从一个城市出发,经过所有城市一次后,再回到起始城市的路径长度最短。这类问题属于组合优化问题,具有NP难特性。 在Matlab环境下,遗传算法的...
这东西是以前觉得QQ农场比较有意思的时候写的,后来还让我同学帮忙分析分析数据, 结果后来太忙了,就一直荒废着,一直荒废到现在连QQ农场都快遗忘了 , 现在将我的分析与源代码 (VC++ 6.0) 发出来,有兴趣可以拿去...
由于TSP问题的普遍性和实际应用价值,寻找高效的解决方案成为优化算法研究的一个重要方向。 本遗传算法代码针对TSP问题进行了优化,代码详细注释,并且支持自定义数据输入,能够适应不同数量的坐标点。用户可以轻松...
算术优化算法AOA与随机森林分类预测建模程序:图表可视化、个性化数据分析解决方案及策略讨论,算数优化算法AOA优化随机森林做二分类和多分类预测建模。 程序内注释详细直接替数据就可以使用。 程序语言为matlab。 ...
支持二分类与多分类预测,Matlab实现,附带多种结果图输出与特征分析,多元宇宙算法MVO优化随机森林做二分类和多分类预测建模。 程序内注释详细直接替数据就可以使用。 程序语言为matlab。 程序直接运行可以出分类...
该模型同时带有paper中的常用的模型评价指标,可以直接拿来替数据做分析,同时各种指标都可以输出,方便记录,如果不会替数据,可以帮忙替数据,该品属于产品,一经出,概不 。 ,核心关键词:随机森林; 多维输入单维...
在本文中,我们将探讨如何利用随机森林算法构建一个多维输入单维输出的回归预测模型,并将介绍模型评价指标的运用和数据处理的便捷方法。 首先,多维输入单维输出的回归预测模型是指模型接收多个特征作为输入,但...
总结起来,本研究通过利用EKF算法设计了一种高效的无人机协同定位滤波器,并通过仿真分析验证了其在实际应用中的可行性和有效性。这一成就不仅在学术上具有重要意义,更在实际应用中展现出巨大的潜力和应用价值。
基于YOLOv9的深度学习道路缺陷检测技术:融合DCNv4、自研BSAM注意力与自适应阈值焦点损失优化算法的实践与效果分析,基于YOLOv9的深度学习道路缺陷检测技术:融合DCNv4、自研BSAM注意力与自适应阈值焦点损失,显著...
【电商数据可视化系统】是一个专为电商商户设计的分析工具,它通过数据可视化技术帮助商家理解和解析商品销售、用户行为等关键数据。该系统由【浙江大学软件学院】开发,项目名为“马云喊我来帮忙”,在天池平台的...
该文件集合提供了一个基于XGBoost算法的多维输入单维输出预测模型,该模型不仅包含了详尽的代码实现和注释,还涉及了深入的理论分析和技术探讨,适合于各个层次的用户学习和应用,并可能包含有关计算机科学、机器...
Jupyter Notebook是一个开源的Web应用程序,允许你创建和共享包含实时代码、可视化和文本来说明的数据科学项目。其设计初衷是支持可执行文档的创建,这种文档能够将代码、数学方程、可视化图表以及解释性文本集成到...
- **适用场景**:当一个系统需要动态地在几种算法中选择一种时,或者一个算法需要根据不同情况作出选择时,可以考虑使用策略模式。 - **实现原理**: - 定义一个接口(`IStrategy`),用于表示不同的算法或策略。 ...
机器学习是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。它专门研究计算机如何模拟或实现人类的学习行为,以获取新的知识或技能,并重新组织已有的知识结构,从而不断改善...
策略模式定义了一系列的算法,并将每一个算法封装起来,使它们可以互相替换。策略模式让算法的变化独立于使用算法的客户。 **应用场景:** - 当一组算法中的每一个都需要被单独封装时; - 当一个对象的行为可以通过...
- 它可能会设定一个最低价和最高价范围,确保砍价活动在可控范围内进行,同时保持吸引力。 - 算法还会考虑防止恶意刷价,确保活动公平性。 3. **源码解析**: - 源码中可能包含数据结构的设计,如用户信息、商品...