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

在排序数组中,找出给定数字的出现次数

发表于: 2012-03-21   作者:bylijinnan   来源:转载   浏览次数:
摘要: public class CountTimesInSortedArray { /** * 题目:在排序数组中,找出给定数字的出现次数,比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。 * 解法:使用二分查找的方法分别找出给定数字的开始和结束位置,最坏情况下时间复杂度为O(logn) */ public static void main(String

public class CountTimesInSortedArray {

	/**
	 * 题目:在排序数组中,找出给定数字的出现次数,比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
	 * 解法:使用二分查找的方法分别找出给定数字的开始和结束位置,最坏情况下时间复杂度为O(logn)
	 */
	public static void main(String[] args) {

		int[] data={0,1,2,2,3,3,3,4,4,4,4,5};
		for(int target:data){
			int time=times(data,target);
			System.out.println(target+","+time+" times");
		}
		
	}
	public static int times(int[] array,int target){
		if(array==null||array.length==0){
			return -1;
		}
		return upTimes(array,target)-downTimes(array,target)+1;
	}
	public static int upTimes(int[] array,int target){
		int low=0;
		int high=array.length-1;
		while(low<high){
			int mid=(low&high)+(low^high)/2+1;//when low=high-1,let mid=high
			int value=array[mid];
			if(value<=target){
				low=mid;
			}else{
				high=mid-1;
			}
		}
		return low;
	}
	public static int downTimes(int[] array,int target){
		int low=0;
		int high=array.length-1;
		while(low<high){
			int mid=(low&high)+(low^high)/2;//when low=high-1,let mid=low
			int value=array[mid];
			if(value>=target){
				high=mid;
			}else{
				low=mid+1;
			}
		}
		return low;
	}
}

在排序数组中,找出给定数字的出现次数

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
问题要求:   数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。   参考资料:
题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的
方法一:先对数组进行排序,再遍历排序后的数组,统计每个数的次数,出现次数最大的数即为要找的数
本文为转载,原文地址是:http://blog.csdn.net/morewindows/article/details/8214003 题目:在一个
看了 教你如何迅速秒杀掉:99%的海量数据处理面试题一文,的确是挺有收获的,特别是对这种海量数据
这个问题关键在于好好分析一些样例如: 给定123这个数,你说这个从1到123所有数字中,1出现的次数是
/* * 统计大串中小串出现的次数 * 举例: * 在字符串"woaijavawozhenaijavawozhendeaijavawozhendeh
有两个数组,需要找出这两个数组之间相同的元素。 package cn.luxh.jpa.test;import java.util.Hash
有两个数组,需要找出这两个数组之间相同的元素。 package cn.luxh.jpa.test;import java.util.Hash
前言 中午在微薄上看道了九度的这道题,把题目先贴出来,分享一下我的解题思路吧 题目描述: 一个整
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号