文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 充分利用題目信息
    • 2.2 位運算
    • 2.3 二分查找

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 <= 數組長度 <= 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(vector<int>& 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(vector<int>& 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(vector<int>& nums) {int l = 0, r = nums.size()-1, mid;while(l < r)//有等于號，則不能退出循環{mid = l+((r-l)>>1);if(nums[mid] == mid)//左邊都不缺l = mid+1;else//不相等，左邊肯定缺了東西，可能在當前位置r = mid;}if(nums[l] == l)//全部有序，前面全部不缺return l+1;return l;//這里寫 r 也可以} };

更簡單的寫法：

class Solution { public:int missingNumber(vector<int>& 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 = mid+1;}}return ans;} };

總結

以上是生活随笔為你收集整理的剑指Offer - 面试题53 - II. 0～n-1中缺失的数字（二分、位运算）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。