基于Java代码实现数字在数组中出现次数超过一半

下文通过几种方法给大家介绍java数组数字出现次数,具体内容如下所示:

方法一:

数组排序,然后中间值肯定是要查找的值。 排序最小的时间复杂度(快速排序)O(NlogN),加上遍历。

方法二:

使用散列表的方式,也就是统计每个数组出现的次数,输出出现次数大于数组长度的数字。

方法三:

出现的次数超过数组长度的一半,表明这个数字出现的次数比其他数出现的次数的总和还多。

考虑每次删除两个不同的数,那么在剩下的数中,出现的次数仍然超过总数的一般,不断重复该过程,排除掉其他的数,最终找到那个出现次数超过一半的数字。这个方法的时间复杂度是O(N),空间复杂度是O(1)。

换个思路,这个可以通过计数实现,而不是真正物理删除。在遍历数组的过程中,保存两个值,一个是数组中数字,一个是出现次数。当遍历到下一个数字时,如果这个数字跟之前保存的数字相同,则次数加1,如果不同,则次数减1。如果次数为0,则保存下一个数字并把次数设置为1,由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多,那么要找的数字肯定是最后一次把次数设为1时对应的数字。

public int MoreHalf(int[] nums) {
int result = 0;
int count = 1;
if (nums.length == 0)
return -1;
result = nums[0];
for (int i = 1; i < nums.length; i++) {
if (count == 0) {
result = nums[i];
count = 1;
continue;
}
if (result == nums[i])
count++;
else
count--;
}
return result;
}

方法四:

改进的快排,前面提到,如果对一个数组进行排序,位于中间位置的那个数字肯定是所求的值。对数组排序的时间复杂度是O(nlog(n)),但是对于这道题目,还有更好的算法,能够在时间复杂度O(n)内求出。

借鉴快速排序算法,其中的Partition()方法是一个最重要的方法,该方法返回一个index,能够保证index位置的数是已排序完成的,在index左边的数都比index所在的数小,在index右边的数都比index所在的数大。那么本题就可以利用这样的思路来解。

通过Partition()返回index,如果index==mid,那么就表明找到了数组的中位数;如果indexmid,表明中位数在[start,index-1]之间。知道最后求得index==mid循环结束。

public int Partition(int[] nums,int start,int end){
int pivotkey = nums[start];
int origin = start;
while(start<end){
while(start<end&&nums[end]>=pivotkey) end--;
while(start<end&&nums[start]<pivotkey) start++;
swap(nums,start,end);
}
swap(nums,start,end);
swap(nums,origin,end);
return end;
}
public int[] swap(int[] ints, int x, int y) {
int temp = ints[x];
ints[x] = ints[y];
ints[y] = temp;
return ints;
}
public int MoreThanHalf(int[] nums){
if(nums.length==0)
return -1;
int start = 0;
int end = nums.length-1;
int index = Partition(nums, start, end);
int mid = nums.length/2;
while(index!=mid){
if(index>mid)
//如果调整数组以后获得的index大于middle,则继续调整start到index-1区段的数组
index = Partition(nums, start, index-1);
else{
//否则调整index+1到end区段的数组
index = Partition(nums, index+1, end);
}
}
return nums[index];
}

以上内容给大家介绍了Java代码实现数字在数组中出现次数超过一半的相关内容,希望对大家有所帮助!

时间: 2016-02-18

实例解析如何正确使用Java数组

一.关于数组的特点 1.在Java中,无论使用数组或集合,都有边界检查.如果越界操作就会得到一个RuntimeException异常. 2.数组只能保存特定类型.数组可以保存原生数据类型,集合则不能.集合不以具体的类型来处理对象,它们将所有对象都按Object类型处理,集合中存放的是对象的引用而不是对象本身. 3.集合类只能保存对象的引用.而数组既可以创建为直接保存原生数据类型,也可以保存对象的引用.在集合中可以使用包装类(Wrapper Class),如Integer.Double等来实现保存

实例讲解Java编程中数组反射的使用方法

什么是反射 "反射(Reflection)能够让运行于JVM中的程序检测和修改运行时的行为."这个概念常常会和内省(Introspection)混淆,以下是这两个术语在Wikipedia中的解释: 内省用于在运行时检测某个对象的类型和其包含的属性: 反射用于在运行时检测和修改某个对象的结构及其行为. 从它们的定义可以看出,内省是反射的一个子集.有些语言支持内省,但并不支持反射,如C++. 内省示例:instanceof 运算符用于检测某个对象是否属于特定的类. if (obj inst

Java数组中的元素删除并实现向前移的代码

废话不多说了,直接给大家贴代码了. 具体代码如下所示: public class Test { /** * Java怎么删除数组中的一个元素并且向前移 * * @param args * @throws IOException */ public static void main(String[] args) { String[] arrays = { "", "", "", "", "" }; Syste

Java数组模拟优先级队列数据结构的实例

优先级队列 如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了.这样,我们就引入了优先级队列 这种数据结构. 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 .对于优先权相同的元素,可按先进先出次序处理或按任意优先

Java对数组实现选择排序算法的实例详解

一. 算法描述     选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟

java中数组的相关知识小结(推荐)

1. 2.数组的命名方法 1)int[]ages=new int[5]; 2) int[]ages; ages=new int[5]; 3)int[]ags={1,2,3,4,5}; 4)int[]ags; ags=new int{1,2,3,4}; 或者 int[]ags=new int{1,2,3,4}; 3.java不支持不同类型的重名数组 4.java中数组的循环赋值 package dierge; public class Shuzu { public static void main

java 创建自定义数组

1.java创建自定义类数组方法: Student []stu = new Student[3]; for(int i = 0; i < 3; i ++) { stu[i] = new Student(); } 2.否则会提示空指针异常 package project; import java.io.*; import java.util.Scanner; class Student { private int id; private String name; private int score

Java中的数组基础知识学习教程

数字 通常情况下,当我们处理数字时,使用原始数据类型,如 byte,int,long,double 等. 示例 int i = 5000; float gpa = 13.65; byte mask = 0xaf; 然而,在开发中,我们会遇到需要使用对象而不是原始数据类型的情况.为了实现这个, Java 为每个原始数据类型提供包装类. 所有的包装类 (Integer, Long, Byte, Double, Float, Short) 是抽象类 Number 的子类. 这种包装是由编译器处理,这个

详解Java中ByteArray字节数组的输入输出流的用法

ByteArrayInputStream 介绍 ByteArrayInputStream 是字节数组输入流.它继承于InputStream. 它包含一个内部缓冲区,该缓冲区包含从流中读取的字节:通俗点说,它的内部缓冲区就是一个字节数组,而ByteArrayInputStream本质就是通过字节数组来实现的. 我们都知道,InputStream通过read()向外提供接口,供它们来读取字节数据:而ByteArrayInputStream 的内部额外的定义了一个计数器,它被用来跟踪 read() 方

Java中动态地改变数组长度及数组转Map的代码实例分享

动态改变数组的长度 /** * Reallocates an array with a new size, and copies the contents * * of the old array to the new array. * * @param oldArray the old array, to be reallocated. * * @param newSize the new array size. * * @return A new array with the same co

浅谈java中集合的由来,以及集合和数组的区别详解

对象多了用集合存,数据多了用数组存. 数组是固定长度的,集合是可变长度的. 集合是:只要是对象就可以存,不管是不是同一种对象 而数组只能存储一种类型的对象 下面是集合的框架: 以上就是小编为大家带来的浅谈java中集合的由来,以及集合和数组的区别详解的全部内容了,希望对大家有所帮助,多多支持我们~

java 中动态代理机制的实例讲解

java 中动态代理机制的实例讲解 在学习Spring的时候,我们知道Spring主要有两大思想,一个是IoC,另一个就是AOP,对于IoC,依赖注入就不用多说了,而对于Spring的核心AOP来说,我们不但要知道怎么通过AOP来满足的我们的功能,我们更需要学习的是其底层是怎么样的一个原理,而AOP的原理就是java的动态代理机制,所以本篇随笔就是对java的动态机制进行一个回顾. 在java的动态代理机制中,有两个重要的类或接口,一个是 InvocationHandler(Interface)

详解java中动态代理实现机制

代理模式是常用的java设计模式,它的特征是代理类与委托类有同样的接口,代理类主要负责为委托类预处理消息.过滤消息.把消息转发给委托类,以及事后处理消息等.代理类与委托类之间通常会存在关联关系,一个代理类的对象与一个委托类的对象关联,代理类的对象本身并不真正实现服务,而是通过调用委托类的对象的相关方法,来提供特定的服务. JAVA各种动态代理实现的比较 接口 interface AddInterface{ int add(int a, int b); } interface SubInterfa

java中以DES的方式实现对称加密并提供密钥的实例

java中以DES的方式实现对称加密并提供密钥的实例 加密原理 DES 使用一个 56 位的密钥以及附加的 8 位奇偶校验位,产生最大 64 位的分组大小.这是一个迭代的分组密码,使用称为 Feistel 的技术,其中将加密的文本块分成两半.使用子密钥对其中一半应用循环功能,然后将输出与另一半进行"异或"运算:接着交换这两半,这一过程会继续下去,但最后一个循环不交换.DES 使用 16 个循环,使用异或,置换,代换,移位操作四种基本运算. 注释都在代码里了,干了: import jav

java中快速创建带初始值的List和Map实例

初始化一个List和Map对象并为期加入值的写法如下: List<String> sList = new ArrayList<String>(); sList.add("str1"); sList.add("str2"); Map<String,String> sMap = new HashMap<String, String>(); sMap.put("k1", "v1");

java 中动态代理详解及实例

Java动态代理相关 先来看静态代理模式代码: package test; public interface Subject { public void doSomething(); } package test; public class RealSubject implements Subject{ public void doSomething() { System.out.println( "call doSomething()" ); } } package test; pu

Java实现MD5加密及解密的代码实例分享

基础:MessageDigest类的使用 其实要在Java中完成MD5加密,MessageDigest类大部分都帮你实现好了,几行代码足矣: /** * 对字符串md5加密 * * @param str * @return */ import java.security.MessageDigest; public static String getMD5(String str) { try { // 生成一个MD5加密计算摘要 MessageDigest md = MessageDigest.g

java中动态代理的实现

动态代理的实现 使用的模式:代理模式. 代理模式的作用是:为其他对象提供一种代理以控制对这个对象的访问.类似租房的中介. 两种动态代理: (1)jdk动态代理,jdk动态代理是由Java内部的反射机制来实现的,目标类基于统一的接口(InvocationHandler) (2)cglib动态代理,cglib动态代理底层则是借助asm来实现的,cglib这种第三方类库实现的动态代理应用更加广泛,且在效率上更有优势. 主要应用的框架: Spring中的AOP,Struts2中的拦截器 具体实现: 1.

java 中动态代理(JDK,cglib)实例代码

java 动态代理实例详解 1.jdk动态代理 /** * */ package com.sinosoft; /** *接口:编写一个委托类的接口,即静态代理的(Apple接口) * */ public interface Apple { public void phoneCall(); } /** * */ package com.sinosoft; /** * 实现一个真正的委托类,即静态代理的(AppleImpl类) * */ public class AppleImpl implemen