剑指 offer代码解析——面试题38数字在排序数组中出现的次数

题目:统计一个有序数组中K出现的次数。

分析:本题最直观的思路就是遍历数组,统计K出现的次数即可。

这种方式的时间复杂度为O(n)。下面我们充分利用“有序数组”这一条件,提高算法的时间效率。

对于一个有序数组,所有的数字K一定都集中在一起,因此只要我们找到这一组K的头和尾就能知道K出现的次数。

此时问题就转化为:在一个有序数组中寻找某个数字。

我们很自然地就想到了二分搜索,在目前所有的搜索算法中,二分搜索具有最高的搜索效率。

对于本题,我们需要进行两次二分搜索,一次寻找K的头,一次寻找K的尾。

二分搜索K头部的过程如下:

1.确定当前数组的中点;

2.若中点<K,则K的起点在后半段;

3.若中点>K,则K的起点在前半段;

4.若中点=K,则判断中点的前一个点是否等于K;

  4.1.若等于K,则K的起点在前半段;

  4.2.若不等于K,则该中点即为K的起点。

寻找K的终点与寻找起点类似。本算法的具体代码如下:

/**
 * 题目:统计一个有序数组中K出现的次数。
 * @author 大闲人柴毛毛
 * @date 2016年3月25日
 */
public class CountKNumber {
	
	/**
	 * 分析:本题最直观的思路就是遍历数组,统计K出现的次数即可。
	 * 这种方式的时间复杂度为O(n)。下面我们充分利用“有序数组”这一条件,提高算法的时间效率。
	 * 
	 * 对于一个有序数组,所有的数字K一定都集中在一起,因此只要我们找到这一组K的头和尾就能知道K出现的次数。
	 * 此时问题就转化为:在一个有序数组中寻找某个数字。
	 * 我们很自然地就想到了二分搜索,在目前所有的搜索算法中,二分搜索具有最高的搜索效率。
	 * 对于本题,我们需要进行两次二分搜索,一次寻找K的头,一次寻找K的尾。
	 * 二分搜索K头部的过程如下:
	 * 1.确定当前数组的中点;
	 * 2.若中点<K,则K的起点在后半段;
	 * 3.若中点>K,则K的起点在前半段;
	 * 4.若中点=K,则判断中点的前一个点是否等于K;
	 * 	4.1.若等于K,则K的起点在前半段;
	 * 	4.2.若不等于K,则该中点即为K的起点。
	 * 寻找K的终点与寻找起点类似。
	 * 
	 * 本算法的具体代码如下:
	 */
	
	/**
	 * 获取数组中K出现的个数
	 * @param a 数组
	 * @param k
	 * @return 返回K出现的个数(若为-1表示获取失败)
	 */
	public static int getKNumber(int[] a,int k){
		//健壮性判断:若数组为空
		if(a==null || a.length<=0){
			System.out.println("数组为空!");
			return -1;
		}
		
		//子数组起点的下标
		int start = 0;
		//子数组终点的下标
		int end = a.length-1;
		
		//K起点的下标
		int k_start = -1;
		//K终点的下标
		int k_end = -1;
		
		//当子数组的长度大于0的时候一直循环,获取k的起点坐标
		while(end-start >= 0){
			//计算中点下标
			int mid = (start+end)/2;
			
			//若a[mid]>k,则k的起点在前半段
			if(a[mid]>k){
				end = mid-1;
			}
			//若a[mid]<k,则k的起点在后半段
			else if(a[mid]<k){
				start = mid+1;
			}
			//若a[mid]=k
			else{
				//若a[mid-1]==k,则说明a[mid]不是k的起点
				if(a[mid-1]==k){
					end = mid-1;
				}
				//若a[mid-1]!=k,则说明a[mid]是k的起点
				else{
					k_start = mid;
					break;
				}
			}
		}
		
		
		//将start、end指向数组的头和尾
		start = 0;
		end = a.length-1;
		//当子数组的长度大于0的时候一直循环,获取k的终点坐标
		while(end-start >= 0){
			//计算中点下标
			int mid = (start+end)/2;
			
			//若a[mid]>k,则k的起点在后半段
			if(a[mid]>k){
				end = mid-1;
			}
			//若a[mid]<k,则k的起点在前半段
			else if(a[mid]<k){
				start = mid+1;
			}
			//若a[mid]=k
			else{
				//若a[mid+1]==k,则说明a[mid]不是k的终点
				if(a[mid+1]==k){
					start = mid+1;
				}
				//若a[mid+1]!=k,则说明a[mid]是k的终点
				else{
					k_end = mid;
					break;
				}
			}
		}
		
		//若未找到k的起点或终点
		if(k_start==-1 || k_end==-1)
			return 0;
		
		//统计k的个数
		return k_end-k_start+1;
	}
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		//构建数组
		int[] a = {0,1,2,3,4,6,7,7,7,7,7,7,8,9};
		//统计k的个数
		System.out.println(getKNumber(a,7));
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

再谈谈列表元素的删除

之前(以及更早之前)都提到了列表元素的删除,也提到过几种方法,有兴趣的朋友可以去看看,其中一种个人比较倾向的写法大概是这个样子(C++):

651
来自专栏小樱的经验随笔

COGS 1299. bplusa【听说比a+b还要水的大水题???】

1299. bplusa ☆   输入文件:bplusa.in   输出文件:bplusa.out 评测插件 时间限制:1 s   内存限制:128 MB ...

2788
来自专栏老司机的技术博客

人人都能学会的python编程教程3:字符串和编码

由于Python源代码也是一个文本文件,所以,当你的源代码中包含中文的时候,在保存源代码时,就需要务必指定保存为UTF-8编码。当Python解释器读取源代码时...

4488
来自专栏游戏开发那些事

【Unity游戏开发】浅谈Lua和C#中的闭包

  目前在Unity游戏开发中,比较流行的两种语言就是Lua和C#。通常的做法是:C#做些核心的功能和接口供Lua调用,Lua主要做些UI模块和一些业务逻辑。这...

1712
来自专栏每日一篇技术文章

Java_面向对象_04

面向对象是Java的核心,面向对象的核心是用人类解决问题的方法对复杂的客观问题进行分析,组织和解答,对于程序员而言,难点在于尽可能正确描述问题的抽象。面向对象的...

653
来自专栏杨熹的专栏

Day 1-Java-imooc-2.变量常量

课程地址:http://www.imooc.com/learn/85 总结图片来自 http://www.imooc.com/article/10535 ? 本...

3365
来自专栏北京马哥教育

Python 开发者不得不知的魔术方法(Magic Method)

来源:j_hao104 my.oschina.net/jhao104/blog/779743 介绍 在Python中,所有以“__”双下划线包起来的方法,都统...

2797
来自专栏软件测试经验与教训

Python学习笔记(二)

2797
来自专栏老九学堂

【超全】C语言初学者必须掌握的关键字!

其实小伙伴在写代码的时候,关键字还是用的比较多的,老九主要就平常中用到的常用关键字进行总结,便于小伙伴们更全面的理解其在代码中的意图。 C语言关键字总结 sta...

3606
来自专栏C/C++基础

C++中引用的本质

引用是C++引入的重要机制,它使原来在C中必须用指针实现的功能有了另一种实现的选择,在书写形式上更为简洁。那么引用的本质是什么,它与指针又有什么关系呢?

561

扫码关注云+社区