题目地址:https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
一个长度为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 <= 数组长度 <= 10000
这道题的思路就是,给你一个数组,数组长度是n-1,数字包括0~n-1等n位数,返回缺失的数字
一、爆破法
爆破法的思路很简单,循环叠加i,如果i不等于nums[i]就说明缺失,如果最后执行完了都没有返回,说明缺失的是n-1;
执行结果如下:
122 / 122 个通过测试用例
状态:通过
执行用时: 0 ms
内存消耗: 38.9 MB
public int missingNumberMe(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if(i != nums[i]) return i;
}
return nums.length;
}
二、二分法
二分法的思路就是,二分查找,
如果左边缺失,那么(0 + length -1) /2的值必然大于nums[(0 + length -1)],
如果右边缺失,则必然是等于(因为缺失的也就是相当于右边大1,那么1/2 =0,所以m和nums[m]肯定对不上),当等于的时候左边指针右移(二分法的右移),当不等于的时候,则右指针左移;
执行结果如下:
122 / 122 个通过测试用例
状态:通过
执行用时: 0 ms
内存消耗: 38.8 MB
public int missingNumber(int[] nums) {
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] == m) i = m + 1;
else j = m - 1;
}
return i;
}
}
思路都很简单,但是没有找到内存很低的方法。。。。。果然越简单的题目越难满分