[剑指offer] 数组中出现次数超过一半的数字
本文首发于我的个人博客:尾尾部落
题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
解题思路
三种解法:
- 法1:借助hashmap存储数组中每个数出现的次数,最后看是否有数字出现次数超过数组长度的一半;
- 法2:排序。数组排序后,如果某个数字出现次数超过数组的长度的一半,则一定会数组中间的位置。所以我们取出排序后中间位置的数,统计一下它的出现次数是否大于数组长度的一半;
- 法3:某个数字出现的次数大于数组长度的一半,意思就是它出现的次数比其他所有数字出现的次数和还要多。因此我们可以在遍历数组的时候记录两个值:1. 数组中的数字;2. 次数。遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。遍历结束后,所保存的数字即为所求。最后再判断它是否符合条件。
参考代码
法1:
import java.util.HashMap; import java.util.Map; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int length = array.length; for(int i=0; i<length; i++){ if(!map.containsKey(array[i])) map.put(array[i], 1); else map.put(array[i], map.get(array[i])+1); } for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if(entry.getValue()*2>length) return entry.getKey(); } return 0; } }
法2:
import java.util.Arrays; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { Arrays.sort(array); int half = array.length/2; int count = 0; for(int i=0; i<array.length; i++){ if(array[i] == array[half]) count ++; } if(count > half) return array[half]; else return 0; } }
法3:
public class Solution { public int MoreThanHalfNum_Solution(int [] array) { int res = array[0], count = 1; for(int i=1; i<array.length; i++){ if(array[i] == res) count++; else{ count--; } if(count == 0){ res = array[i]; count = 1; } } count = 0; for(int i=0; i<array.length; i++){ if(array[i] == res) count++; } return count > array.length/2 ? res : 0; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
TensorFlow 高效编程
TensorFlow 高效编程 原文:vahidk/EffectiveTensorflow 译者:FesianXu、飞龙 协议:CC BY-NC-SA 4.0 一、TensorFlow 基础 TensorFlow 和其他数字计算库(如 numpy)之间最明显的区别在于 TensorFlow 中操作的是符号。这是一个强大的功能,这保证了 TensorFlow 可以做很多其他库(例如 numpy)不能完成的事情(例如自动区分)。这可能也是它更复杂的原因。今天我们来一步步探秘 TensorFlow,并为更有效地使用 TensorFlow 提供了一些指导方针和最佳实践。 我们从一个简单的例子开始,我们要乘以两个随机矩阵。首先我们来看一下在 numpy 中如何实现: import numpy as np x = np.random.normal(size=[10, 10]) y = np.random.normal(size=[10, 10]) z = np.dot(x, y) print(z) 现在我们使用 TensorFlow 中执行完全相同的计算: import TensorFlow as...
- 下一篇
Java对象的深度拷贝实现
1. 说明 Java对象复制可分为浅拷贝(shallow copy)和深度拷贝(deep copy)两种。浅拷贝指从源对象中将值复制出来,因此产生的拷贝对象与源对象并不是独立的。如源对象存在引用属性(reference),此时的拷贝对象和源对象的相同引用属性都指向同一个对象,修改引用属性对象的内容,对于拷贝对象和源对象都可见。深度拷贝指将源对象的对象图中所有对象都被拷贝一次,因此产生的拷贝对象与源对象是独立的。即引用属性的拷贝,也是将引用指向的对象拷贝一份。源对象的对象图中任何属性的改变,并不会影响拷贝对象的属性。 理解上面的含义后,我们下面将比较两种拷贝方式,并讨论4种深度拷贝的实现。 2. 准备 2.1 依赖 我们将使用Maven来管理项目依赖,需要引入Gson,JackSon,Apache Commons Lang。 <dependency> <groupId>com.google.code.gson</groupId> <artifactId>gson</artifactId> <version>2.8.5...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8编译安装MySQL8.0.19
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7