0～n-1で欠落した数字--二分法

0x01.に質問
長さn−1のインクリメンタルソート配列のすべての数字は一意であり、各数字は0〜n−1の範囲内である.範囲0～n-1内のn個の数字のうち、その配列に1個しかない数字がある場合は、この数字を見つけてください.入力例:[0,1,2,3,4,5,6,7,9]出力例:8

C++    ：     int missingNumber(vector<int>& nums) 

0x02.簡単な分析
これは実はとても簡単な問題で、テーマを読んで、大意は(n-1をnに変換してもっと理解しやすい):

長さnのインクリメント配列には、0-nの中のnが含まれており、中には入っていないものを見つけています.

テーマはとてもはっきりしていて、1つの数を探して、しかも1つの増加する配列で、そこで简単な考え方はあって、この数は3つの可能性しかなくて、配列の第1位、最后の1位、真ん中で、そこで私达は分类して判断することができます.

は、1位が0であるかどうかを判断し、いいえ、0が少なくなったに違いありません.

その後、中間の数字が前の桁に1を加えたものかどうかを判断し、この数が1を減らしたものではない.

サイクルが終わっても見つからない場合は、最後の数はありません.

普通の考え方は簡単ですが、ここではもっと巧みな二分法を使います.
私たちは発見して、この配列は実は2つの部分に分けることができて、第1部分はnums[i]=iを満たして、この中はすべて連続して、第2部分は満足していないで、第1の満足していない数は1を減らして私たちが探している数です.
これは秩序化されたシーケンスであり,この最初の満たされていない数を二分法を用いて探索することができる.

leftは左がnums[i]=iを満たす部分を制御し、rightは右が満たさない部分を制御する.

は毎回中を取って、もしnums[mid]=midを満たすならば、探す数を説明するのは右側で、left=mid+1で、説明を満たさないのは左で、right=mid-1です.

最後にleft>rightのとき、nums[left]は最初に満たされていない数であり、私たちが要求した答えはnums[left]-1であり、実際にはleftである.

0x03.解決コード–通常遍歴--O(N)

int missingNumber(vector<int>& nums) {
    if(nums[0]!=0) return 0;
    for(int i=1;i<nums.size();i++){
        if(nums[i]!=nums[i-1]+1) return nums[i]-1;
    }
    return nums.size();
}

0 x 04,解決コード–二分法--O(logN)

int missingNumber(vector<int>& nums) {
    int left=0;
    int right=nums.size()-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(nums[mid]==mid) left=mid+1;
        else right=mid-1;
    }
    return left;
}

ATFWUS --Writing By 2020–03–27