当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-74-数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字

发表于: 2012-02-11   作者:bylijinnan   来源:转载   浏览:
摘要: public class OcuppyMoreThanHalf { /** * Q74 数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字 * two solutions: * 1.O(n) * see <beauty of coding>--每次删除两个不同的数字,不改变数组的特性 * 2.O(nlogn) * 排序。中间

public class OcuppyMoreThanHalf {

	/**
	 * Q74 数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字
	 * two solutions:
	 * 1.O(n)
	 * see <beauty of coding>--每次删除两个不同的数字,不改变数组的特性
	 * 2.O(nlogn)
	 * 排序。中间那个元素就是所求
	 */
	public static void main(String[] args) {
		int[] a={4,3,4,2,4,5,4,4};
		
		int result=find(a);
		System.out.println(result);
		
		result=findAfterSort(a);
		System.out.println(result);
	}

	public static int find(int[] a){
		if(a==null||a.length==0){
			return -1;
		}
		int len=a.length;
		int candidate=a[0];
		int times=1;
		for(int i=1;i<len;i++){
			if(candidate!=a[i]){
				times--;
				if(times==0){
					candidate=a[i];
					times=1;
				}
			}else{
				times++;
			}
		}
		return candidate;
	}
	public static int findAfterSort(int[] a){
		if(a==null||a.length==0){
			return -1;
		}
		myQuickSort(a,0,a.length-1);
		int midIndex=a.length/2;
		return a[midIndex];
	}
	public static void myQuickSort(int[] a,int start,int end){
		if(start>=end){
			return;
		}
		boolean flag=false;
		int s=start,e=end;
		while(s<e){
			if(a[s]>a[e]){
				Helper.swap(a,s,e);
				flag=true;
			}
			if(flag){
				s++;
			}else{
				e--;
			}
		}
		myQuickSort(a,start,s-1);
		myQuickSort(a,e+1,end);
	}
}


java-74-数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
方法一:先对数组进行排序,再遍历排序后的数组,统计每个数的次数,出现次数最大的数即为要找的数
问题要求:   数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。   参考资料:
题目1349:数字在排序数组中出现的次数 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:919 解
一、题目:数字在排序数组中出现的次数 题目:统计一个数字在排序数组中出现的次数。例如输入排序数
题目: 统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于3在
1、8*8的棋盘上面放着64个不同价值的礼物,每个小的棋盘上面放置一个礼物(礼物的价值大于0),一个
来自剑指offer 分析: 如果整型数组中只有一个数字出现一次,我们只需将数组中每个元素依次做异或操
/* * 程序的版权和版本声明部分 * Copyright (c)2012, 烟台大学计算机学院学生 * All rightsreserve
时间限制:1 秒内存限制:32 兆特殊判题:否 题目描述: 把一个数组最开始的若干个元素搬到数组的末
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号