我是靠谱客的博主 爱笑盼望,这篇文章主要介绍剑指offer:面试题53—在排序数组中查找数字,现在分享给大家,希望可以做个参考。

题目一:数字在排序树组中出现的次数

统计一个数字在排序数组中出现的次数。

解决:

二分查找,确定数组中等于K值的左右下标。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int GetNumberOfK(int [] array , int k) { int left=-1,right=-1,start=0,end=array.length-1,mid=0; while(start<=end){ mid=(start+end)/2; if(array[mid]<k){ start=mid+1; }else if(array[mid]>k){ end=mid-1; }else{ end=mid-1; left=mid; } } start=0; end=array.length-1; while(start<=end){ mid=(start+end)/2; if(array[mid]<k){ start=mid+1; }else if(array[mid]>k){ end=mid-1; }else{ start=mid+1; right=mid; } } if(right==-1) return 0; return right-left+1; }

题目二:0到n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0到n-1内。在范围0到n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

解决:

1.暴力:求0到n-1的数字之和,在计算数组中所有数字之和,相减,就是结果。

2.但给定条件是递增数组,可利用这个条件进行优化,即判断数组下标和数字是否相等,利用二分查找。

 

题目三:数组中数值和下标相等的元素

假设一个单调递增数组里的每个元素都是整数并且是唯一的,请实现一个函数,找出数组中任意一个数值等于其下标的元素。

解决:

使用二分查找。

最后

以上就是爱笑盼望最近收集整理的关于剑指offer:面试题53—在排序数组中查找数字的全部内容,更多相关剑指offer内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(91)

评论列表共有 0 条评论

立即
投稿
返回
顶部