剑指 Offer 53 - II. 0~n-1中缺失的数字
2021/5/1 18:28:05
本文主要是介绍剑指 Offer 53 - II. 0~n-1中缺失的数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
II. 0~n-1中缺失的数字
- 有关题目
- 题解
题目链接: 0~n-1中缺失的数字
有关题目
一个长度为n-1的递增排序数组中的所有数字都是唯一的, 并且每个数字都在范围0~n-1之内。 在范围0~n-1内的n个数字中有且只有一个数字不在该数组中, 请找出这个数字。
示例 1: 输入: [0,1,3] 输出: 2
示例 2: 输入: [0,1,2,3,4,5,6,7,9] 输出: 8
题解
1、
有的解法跟这个很像面试题 17.04. 消失的数字
2、二分查找
参考题解
根据题意,数组可以按照以下规则划分为两部分。
左子数组: nums[i] == i ;
右子数组: nums[i] != i;
返回值: 跳出时,变量 i 和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i即可。
int missingNumber(int* nums, int numsSize){ int l = 0; int r = numsSize - 1; int mid = 0; // 0 1 2 3 5 6 7 8 9--9 // r = 3 //mid 1 // l = 2 //mid = 2 //l = 3 //l = 4 while(l <= r) { mid = (l + r) / 2; if (nums[mid] == mid)//一定在[mid + 1,r]边界内 l = mid + 1; else//一定在[l,mid - 1] r = mid - 1; } return l; }
时间复杂度 O(log N): 二分法为对数级别复杂度。
空间复杂度 O(1): 几个变量使用常数大小的额外空间。
这篇关于剑指 Offer 53 - II. 0~n-1中缺失的数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现