淘宝美工网站怎么做,佛山专业建站公司哪家好,优质东莞网站制作公司,.net网站开发教程文章目录1. 题目2. 解题2.1 充分利用题目信息2.2 位运算2.3 二分查找1. 题目
一个长度为n-1的递增排序数组中的所有数字都是唯一的#xff0c;并且每个数字都在范围0#xff5e;n-1之内。在范围0#xff5e;n-1内的n个数字中有且只有一个数字不在该数组中#xff0c;请找出…
文章目录1. 题目2. 解题2.1 充分利用题目信息2.2 位运算2.3 二分查找1. 题目
一个长度为n-1的递增排序数组中的所有数字都是唯一的并且每个数字都在范围0n-1之内。在范围0n-1内的n个数字中有且只有一个数字不在该数组中请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8限制
1 数组长度 10000来源力扣LeetCode 链接https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 充分利用题目信息
nums[i] ! i就是缺少的数 i 都不少的话少的就是n nums.size()class Solution {
public:int missingNumber(vectorint nums) {for(int i 0; i nums.size(); i)if(nums[i] ! i)return i;return nums.size();//有个例子是 [0],答案预期 1}
};2.2 位运算
class Solution {
public:int missingNumber(vectorint nums) {int i, ans nums.size();for(i 0; i nums.size(); i)ans ans^i^nums[i];return ans;}
};2.3 二分查找
class Solution {
public:int missingNumber(vectorint nums) {int l 0, r nums.size()-1, mid;while(l r)//有等于号则不能退出循环{mid l((r-l)1);if(nums[mid] mid)//左边都不缺l mid1;else//不相等左边肯定缺了东西可能在当前位置r mid;}if(nums[l] l)//全部有序前面全部不缺return l1;return l;//这里写 r 也可以}
};更简单的写法
class Solution {
public:int missingNumber(vectorint nums) {int l 0, r nums.size()-1, mid, ans;while(l r){mid l((r-l)1);if(nums[mid] mid){ans nums[mid]-1;r mid-1;}else{ans nums[mid]1;l mid1;}}return ans;}
};
