首页 > 编程语言 > 详细

数组在排序数组中出现的次数

时间:2015-08-20 01:32:25      阅读:244      评论:0      收藏:0      [点我收藏+]

题目

统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于3在这个数组中出现了4次,因此输入4.

思路

首先第一种思路,必然是遍历数组,然后定义累加器,但是这种时间复杂度为O(n)
我们注意到数组是排序的,我们可以利用而分查找的特点,首先将第一个3找到,然后找出最后一个3,相减即可。

代码

public static int getFirst(int[] data,int start,int end,int key)
	{
		if(data == null)return -2;
		if(start > end )
			return -1;
		
		int mid = ( start+end )/2;
		int midData = data[mid];
		
		if(midData == key)
		{
			if(( mid >0 && data[mid-1] !=key)|| mid==0)
				return mid;
			else 
				return getFirst(data, start, mid-1, key);//可以修改让其只返回一个return
				
		}else if(midData > key)
			
			return getFirst(data, start, mid-1, key);
		
		else 
			return getFirst(data, mid+1, end, key);
			
	}
	
	public static int getLast(int[] data,int start,int end,int key)
	{
		if(data == null)return -2;
		if(start > end)return -1;
		
		int mid = (start+end)/2;
		int midData = data[mid];
		
		if(midData == key)
		{
			if((  mid < data.length-1 && data[mid+1] !=key )|| mid == data.length-1 )
				return mid;
			else 
				return getLast(data, mid+1, end, key);
				
		}
		else if(midData > key)
			return  getLast(data, start, mid-1, key);
		else 
			return getLast(data, mid+1, end, key);
		
		
	}
	public static void getNumber(int[] data,int key)
	{
		int startIndex = getFirst(data, 0, data.length-1,key);
		int endIndex = getLast(data, 0, data.length-1,key);
		if(startIndex >-1 && endIndex > -1)
			System.out.println(endIndex-startIndex+1);
		else 
			System.out.println("no");
	}


版权声明:本文为博主原创文章,转载请注明出处。

数组在排序数组中出现的次数

原文:http://blog.csdn.net/u014307117/article/details/47791703

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!