0~n-1中缺失的数字--------二分法的处理

技术文章 1年前 (2020) 完美者
718 0

标签:规则   处理   else   http   number   font   iss   二分法查找   数组   

技术图片

 

 解题思路:

  • 排序数组中的搜索问题,首先可以想到二分法解决。
  • 根据题意,数组可以按照下面的规则进行划分为两部分。

                左子数组:nums[i]=i;

                右子数组:nums[i]!=i;

  • 缺失的数字等于“右子数组的首位元素”对应的索引;因此考虑使用二分法查找“由子数组的首位元素”。

技术图片

 

技术图片

 

 技术图片

技术图片

 

 技术图片

 

 技术图片

 

 技术图片

 

 技术图片

 

 技术图片

 

 

 1 int missingNumber(int* nums, int numsSize){
 2     int i=0,j=numsSize-1;
 3     int m;
 4     while(i<=j)
 5     {
 6         m=(i+j)/2;
 7         if(nums[m]==m)
 8         {
 9             i=m+1;
10         }
11         else
12         {
13             j=m-1;
14         }
15     }
16     return i;
17 }

 

0~n-1中缺失的数字--------二分法的处理

标签:规则   处理   else   http   number   font   iss   二分法查找   数组   

原文地址:https://www.cnblogs.com/sbb-first-blog/p/13617103.html

版权声明:完美者 发表于 2020-09-17 13:50:32。
转载请注明:0~n-1中缺失的数字--------二分法的处理 | 完美导航

暂无评论

暂无评论...