剑指 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 条评论
登录 后参与评论

相关文章

来自专栏程序你好

二叉树搜索树(程序员都知道)

931
来自专栏北京马哥教育

这段代码很Pythonic | 相见恨晚的 itertools 库

1503
来自专栏数据结构与算法

P1732 活蹦乱跳的香穗子

题目描述 香穗子在田野上调蘑菇!她跳啊跳,发现自己很无聊,于是她想了一个有趣的事情,每个格子最多只能经过1次,且每个格子都有其价值 跳的规则是这样的,香穗子可以...

3607
来自专栏Golang语言社区

Golang语言社区--Go语言基础第二节变量

大家好,我是社区主编cserli(或者大家叫我彬哥也可以),Golang语言社区一直致力于Go语言相关技术干货的分享,希望初学者可以少走些弯路,我...

59827
来自专栏架构说

折半查找部分有序

部分有序 本周qq群有人咨询 Search in Rotated Sorted Array 来源: https://leetcode.com/proble...

2749
来自专栏小白客

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

2724
来自专栏大数据和云计算技术

#算法基础#选择和插入排序

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第二篇《选择和插入排序》,非常赞!希望对大家有帮助,大家会喜欢! 系列文章: 由快速排序到分治思想 ...

3306
来自专栏落影的专栏

程序员进阶之算法练习(二十五)

前言 算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意: 给出a、b、c三种材料,可以1:2:4组成...

3669
来自专栏移动开发面面观

排序备忘

排序是算法的一项基础能力,也是面试必考题。如何写一个恰当的排序,也是一个软件工程师的基本必备技能。

481
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

2456

扫码关注云+社区