首页 > 代码库 > 算法笔记_131:出现次数超过一半的数(Java)
算法笔记_131:出现次数超过一半的数(Java)
目录
1 问题描述
2 解决方案
2.1 每次删除两个不同的数
2.2 记录两个值
1 问题描述
数组中有一个数出现的次数超过了数组长度的一半,请找出这个数。
2 解决方案
2.1 每次删除两个不同的数
具体代码如下:
package com.liuzhen.practice; public class Main { public int getResult(int[] A) { //找到两个不相等的元素,将这两个元素变为0 for(int start = 0, i = 1;i < A.length;i++) { while(A[start] == 0) { start++; } if(A[start] != A[i] && start < i) { A[start] = 0; A[i] = 0; start++; } } int result = 0; for(int i = 0;i < A.length;i++) { if(A[i] != 0) { result = A[i]; break; } } return result; } public static void main(String[] args) { Main test = new Main(); int[] A = {1,2,3,4,5,6,7,1,1,2,3,2,2,2,2,2}; System.out.println(test.getResult(A)); } }
运行结果:
2
2.2 记录两个值
具体代码如下:
package com.liuzhen.practice; public class Main1 { public int FindOneNumber(int[] A) { int result = A[0]; int count = 1; for(int i = 1;i < A.length;i++) { if(count == 0) { result = A[i]; count = 1; } else { if(A[i] == result) count++; else count--; } } return result; } public static void main(String[] args) { Main1 test = new Main1(); int[] A = {1,2,3,4,5,6,7,1,1,2,3,2,2,2,2,2}; System.out.println(test.FindOneNumber(A)); } }
运行结果:
2
参考资料:
1.《编程之法面试和算法心得》 July 著
算法笔记_131:出现次数超过一半的数(Java)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。