剑指 Offer 53 - II. 0~n-1中缺失的数字
2022/1/18 23:33:39
本文主要是介绍剑指 Offer 53 - II. 0~n-1中缺失的数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer 53 - II. 0~n-1中缺失的数字
首先观察题目给我们的条件,有序递增数组中找元素,比较自然地会往二分上联系。一般的二分,我们找到答案后会直接返回,但这里的二分,我们需要不断缩小空间,直到找到为止。
class Solution { public int missingNumber(int[] nums) { int l= 0; int r= nums.length - 1; while (start < end) { int mid = l + (r - l) / 2; if (nums[mid] == mid) { //如果nums[mid] == mid也就是说当前元素的 //下标等于他自己,比如数组[0,1,2,3,4,5]每 //个元素的下标都等于他自己,说明[l,mid] //没有缺少任何数字,那么缺少的肯定是在[mid+1,r] l = mid + 1; } else { //如果当前元素的下标不等于他自己,比如[0,1,2,4]中 //nums[3]==4,说明说明缺少的数字就在这个区间内 r = mid; } } //如果类似于[0,1,2,3]这种start指向了数组的最后一个,我们让他加1 return l == nums[l] ? l + 1 : l; } }
二分的时间复杂度为\(O(nlogn)\),空间复杂度为\(O(1)\)。
再分析时间复杂度更低的算法,由于每个数字都只出现了一次,由此考虑位运算,先从0-n之间的所有数异或,再与原数组中的数字异或一次,这样得到的结果即为丢失的数字。
class Solution { public int missingNumber(int[] nums) { int ans = 0, n = nums.length; for(int i = 1; i <= n; i++) { ans ^= i; } for(int num : nums) { ans ^= num; } return ans; } }
这篇关于剑指 Offer 53 - II. 0~n-1中缺失的数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20接口模块封装入门教程
- 2024-09-20请求动作封装入门教程
- 2024-09-20登录鉴权学习:新手入门教程
- 2024-09-20后台管理开发学习:新手入门指南
- 2024-09-20后台管理系统开发学习:从入门到实践
- 2024-09-20后台开发学习:从入门到初级实战指南
- 2024-09-20后台综合解决方案学习:从入门到实践
- 2024-09-20接口模块封装学习入门指南
- 2024-09-20请求动作封装学习:新手入门教程
- 2024-09-20登录鉴权入门:打造安全的用户认证系统