最初のN個の自然数の配列の1,2,3個の欠損番号を見つける

Question

配列がソートされていると仮定すると、最初のN個の自然数の配列に1、2、

再び、アレイがソートされると仮定すると、次のコードは、私は同じことを行う多くの回答を見てきました

function findMissingNumbers(array) { 
     for (var i = 0; i < array.length; i++) { 
      if (array[i] != (i + 1)) { 
       return i + 1; 
      } 
     } 
     return 'no missing numbers found'; 
    } 

    var missingArr = [1, 3, 4, 5, 6, 7]; 
    console.log(findMissingNumbers(missingArr)); 

（原因returnステートメントに）欠けている一つの値を返すために動作します（1を見つけます期待値の総和から期待値を差し引いて欠損値を求めることで、欠損値を見つけることができます。

私は私のようにiを使ってこのコードがうまくいかないことを知っています。もしarr [i]！= i + 1なら欠けている値を新しい配列にプッシュして書きましたが、最初の欠損値の正しい値のみを返します。

どのようにこの問題にアプローチしますか？

Answer 1

欠番を返すために提供配列とその配列をArray.from()フィルタを使用してから配列を作成し、アレイ内で最小とmaxium数を検索します。

function findMissingNumbers(arr) { 
 
    var min = Math.min(...arr); 
 
    var max = Math.max(...arr); 
 
    var all = Array.from(Array(max - min + 1), (e, i) => i + min) 
 
    return all.filter(e => !arr.includes(e)) 
 
} 
 

 
console.log(findMissingNumbers([1, 3, 4, 5, 6, 7])); 
 
    console.log(findMissingNumbers([10, 16, 8]));

Answer 2

ここでは2つの変更が必要です。

1. forループの最初の繰り返しで数値を返す代わりに、関数から配列を戻します。
2. 見逃した番号を追跡するための新しい変数を作成します。以下は

更新されたコードスニペットです：

function findMissingNumbers(array) { 
    var resultsArray = []; 
    var missedNumbers = 0; 

    for (var i = 0; i < array.length; i++) { 
     var expectedValue = i + 1 + missedNumbers; 

     if (array[i] != expectedValue) { 
      var segmentCountOfMissedNumbers = array[i] - expectedValue; 

      for (var ii = 0; ii < segmentCountOfMissedNumbers; ii++) { 
       resultsArray.push(expectedValue + ii); 
      } 
      missedNumbers = missedNumbers + segmentCountOfMissedNumbers; 
     } 
    } 

    if (resultsArray.length > 0) { 
     return resultsArray; 
    } else { 
     return 'no missing numbers found'; 
    } 
} 

var missingArr = [3, 5, 9]; 
console.log(findMissingNumbers(missingArr)); 

Answer 3

あなたは動作するはずArray.prototype.reduce()、do..whileループ

var missingArr = [1, 3, 4, 5, 6, 7, 9]; 
 
var res = []; 
 

 
missingArr.reduce(function(a, b) { 
 
    var i = a + 1; 
 
    if (i !== b) { 
 
    do { 
 
     res.push(i++) 
 
    } while (i < b); 
 
    } 
 
    return b 
 
}); 
 

 
console.log(res);

Answer 4

つ以上の実装を使用することができます。時間の複雑さの面ではO(n)である必要があります。

function findMissingNumbers(array) { 
 
\t  var missingNumbers = []; 
 
\t  var endInteger = array[array.length - 1]; 
 
\t \t var missingNumberCounter = 0; 
 
\t \t 
 
     for (var i=0; i < endInteger; i++) { 
 
      if (array[i - missingNumberCounter] != (i + 1)) { 
 
       missingNumbers.push(i + 1); 
 
\t \t missingNumberCounter++; 
 
      } 
 
     } 
 
     return missingNumbers; 
 
     
 
    } 
 

 
var missingArr = [1, 3, 4, 5, 6, 7]; 
 
var missingArr2 = [2, 3, 4, 9, 10, 11]; 
 
console.log(findMissingNumbers(missingArr)); 
 
console.log(findMissingNumbers(missingArr2));

Answer 5

あなたはここにSet

function* findMissingNumbers(array) { 
 
    var numbers = new Set(array), 
 
     i = 1; 
 

 
    while (numbers.size) { 
 
     if (numbers.has(i)) { 
 
      numbers.delete(i); 
 
     } else { 
 
      yield i; 
 
     } 
 
     i++; 
 
    } 
 
} 
 

 
console.log([...findMissingNumbers([1, 3, 4, 5, 6, 7])]); 
 
console.log([...findMissingNumbers([6, 7])]); 
 
console.log([...findMissingNumbers([1, 2, 3, 4, 5, 6, 7])]);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 6

を使用することができます（他の）非ES6ソリューションです。内部ループはおそらく、最後の行の次のものとして並べ替えを必要としないように修正することができます。

内ループにかかわらず、最悪の場合、O（n）x 2で実行されるべきであり、これは1で境界付けされた配列と、配列の最大値とを比較すると、内側ループは複数回1つの「ギャップ」よりも

ループはthis non-ES6 implementationよりもエレガントではないかもしれませんが、一方、私の場合、返される配列以外の変数は導入されないという利点があります。

function findMissingNumbers(array) { 
    var missingNumbers = []; 

    for (var i=0, n=array.length; i<n; i++) { 
     if (array[i] > (i + 1 + missingNumbers.length)) { 
      for (j=1, k = array[i] - (i + 1 + missingNumbers.length); j<=k; j++) { 
       missingNumbers.push(array[i] - j); 
      } 
     } 
    } 

    missingNumbers.sort(); 
    return missingNumbers; 
} 

var missingArr = [1, 4, 5, 6, 7, 9]; 
console.log(findMissingNumbers(missingArr).join(",")); //2,3,8