【Offer】[53-2] 【0~n-1中缺失的数字】
2024-08-29 02:05:48
题目描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
[牛客网刷题地址] 无
思路分析
- 可以利用数学公式，等差数列公式，先求出0~n-1的和s1，然后再遍历整个数组，将他们的值相加得到s2，然后，所求的值为s1-s2；
- 由于是递增的数组，而且，下标0对应元素为0，下标n对应元素为n，由于其中缺少一个元素，导致后面的下标和其对应元素不相等，所以将问题转化为，查找第一个下标与元素之不相等的值，可以利用二分查找法，判断中间元素的值与下标：
- 如果相等，则下一轮比较右半部分；
- 如果不相等，并且它前一个元素的值和其对应下标相等，那么，此值就是要找的元素，如果它前一个元素的值和其对应下标不相等，那么，就查找左边部分。
测试用例
- 功能测试：缺失的数字位于数组的开始、中间或者末尾。
- 边界值测试：数组中只有一个数字0。
- 特殊输入测试：表示数组的指针为nullptr指针。
Java代码
public class Offer053_02 {
public static void main(String[] args) {
test1();
test2();
test3();
}
public static int GetMissingNumber(int[] array) {
return Solution1(array);
}
private static int Solution1(int[] array) {
if(array==null || array.length<=0) {
return -1;
}
int start = 0;
int end = array.length-1;
while(start< end) {
int mid = (start+end)>>1;
if(array[mid]!=mid) {
if(mid == 0 || array[mid-1]==mid-1) {
return mid;
}
end = mid-1;
}else {
start = mid+1;
}
}
return -1;
}
private static void test1() {
int[] arr = {0,1,2,3,4,5,6,7,9,10,11};
System.out.println(GetMissingNumber(arr));
}
private static void test2() {
int[] arr = {1,2,3,4,5,6,7,8,9,10,11};
System.out.println(GetMissingNumber(arr));
}
private static void test3() {
int[] arr = {0};
System.out.println(GetMissingNumber(arr));
}
}
代码链接
最新文章
- Puzzle 面向服务/切面(AOP/IOC)开发框架 For .Net
- NCreport报表控件教程：设计页眉和页脚
- centos7安装
- hdu 4193 - Non-negative Partial Sums(滚动数列)
- canvas draw a image
- [转]ASP.NET MVC 4 (九) 模型绑定
- Linux和Windows路由配置
- Service代码示例
- JDK安装配置问题
- [GRYZ]寒假模拟赛
- IIS连接数
- Git常用命令汇总
- Ubuntu14.04 安装QQ(国际版)
- java_爬虫_从腾讯视频播放界面爬取视频真实地址
- Android毛玻璃模糊化效果处理
- Spring 通过Java代码装配bean
- ZT 互联网——降级论
- 制作Linux内核
- mysql数据导入的时候提示Got a packet bigger than 'max_allowed_packet' bytes
- oracle 物化视图 ORA-23413: 表 "xxx"."xx" 不带实体化视图日志