【二分查找专题】剑指 Offer 53 – II. 0～n-1中缺失的数字

共以下 9 个回答

• 小肸 永久会员 2023年9月3日 下午4:52

  class Solution {
      public int missingNumber(int[] nums) {
          int l = 0, r = nums.length - 1;
          while (l <= r) {
              int mid = (l + (r - l) / 2);
              if (nums[mid] == mid) {//说明缺失的数字在右半部分
                  l = mid + 1;
              } else {//说明缺失的数字在左半部分
                  r = mid - 1;
              }
          }
          //最后l指向缺失的数字本来位于的位置，所以返回l
          return l;     
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sc_Yang 普通 2023年9月2日 下午7:00

  暴力搜索

  class Solution {
  public:
      int missingNumber(vector<int>& nums) {
          if(nums.size()==0) return 0;
          if(nums[0]==1) return 0;
          int i=1;
          for(i=1; i<nums.size(); i++){
              if(nums[i]-nums[i-1]!=1){
                  return i;
              }
          }
          // 如果当前已有的数列均是等差，那意味着只少最后一位，则将没有的最后一位进行返回
          return i;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• Sheng 永久会员 2023年9月2日 下午5:23

  这个题翻译一下，找出数组中第一个大于索引值得元素的索引

      //在范围0~n-1内的n个数字中有且只有一个数字不在此数组内，请找出这个数字
      public int missingNumber(int[] nums) {
          if(nums[nums.length-1] <= nums.length-1) return nums.length;
  
          int l = 0;
          int r = nums.length - 1;
          int mid = -1;
          while(l < r) {
              mid = (l + r) / 2;
              if(nums[mid] == mid) {
                  l = mid + 1;
              }
              else if(nums[mid] > mid) {
                  r = mid;
              }
          }
          return l;
      }
  

  0 赞同 0 条回复

  登录以回复
• sincere 普通 2023年8月31日 下午2:55

  • 思路：二分查找左闭右开，如果`num[mid]==mid`说明[left,mid]区间都没问题，left=left+1；不等于则说明肯定有问题，right=mid
  • 复杂度：时间复杂度O(logn)，空间复杂度O(1)

  class Solution {
      public int missingNumber(int[] nums) {
          int left = 0;
          int right = nums.length;
          while (left < right) {
              int mid = left + (right - left) / 2;
              if (nums[mid] == mid) {
                  left = mid + 1;
              } else {
                  right = mid;
              }
          }
          return left;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年8月29日 上午12:13

  处理好边界

  class Solution {
      public int missingNumber(int[] nums) {
          int left = 0, right = nums.length-1;
          while(left <= right){
              int mid = left + (right - left)/2;
              if(nums[mid] == mid){
                  left = mid + 1;
              }else{
                  right = mid - 1;
              }
          }
          return left;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• JustRtn 普通 2023年8月28日 下午6:46

  二分查找：O(log(n))

  class Solution {
  public:
      int missingNumber(vector<int>& nums) {
          int low = 0;
          int high = nums.size() - 1;
  
          while (low <= high) {
              int mid = low + ((high - low) >> 1);
              if (nums[mid] == mid) {
                  low = mid + 1;
              } else {
                  if (mid == 0 || (nums[mid - 1] == mid - 1)) {
                      return mid;
                  } else {
                      high = mid - 1;
                  }
              }
          }
          return nums.size();
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• c 普通 2023年8月27日 下午9:57

  二分查找

  class Solution {
      public int missingNumber(int[] nums) {
          int res = nums.length;
          int l = 0;
          int r = nums.length-1;
          while(l<=r){
              int m = l+((r-l)>>1);
              if(m==nums[m]){
                  l=m+1;
              }else{
                  res=m;
                  r = m - 1;
              }
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 行动派小彩笔 普通 2023年8月27日 下午9:19

  // 二分思想，查找的元素就是mid
  // 时间复杂度O(log n)
  class Solution {
  public:
      int missingNumber(vector<int>& nums) {
          int left = -1;
          int right = nums.size();
          while(left+1!=right)
          {
              int mid = (left+right)/2;
              if(nums[mid]==mid) left=mid;
              else right=mid;
          }
          return right;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年8月27日 下午7:11

  正常情况下，nums[mid]=mid; 以此为条件，套用地哥的二分查找模板即可

  class Solution {
      public int missingNumber(int[] nums) {
          int n = nums.length + 1;
          int l = 0;
          int r = nums.length - 1;
          if (nums[r] == n - 2) {
              return n - 1;
          }
          while (l < r) {
              int mid = (r - l) / 2 + l;
              if (nums[mid] > mid) {
                  r = mid;
              } else {
                  l = mid + 1;
              }
          }
          return l;
      }
  }
  

  0 赞同 0 条回复

  登录以回复