配列に入ってない数で最小の値を求める

Question

いつもお世話になっております。

今日はある問題に関してお聞きしたいです。

ある問題の内容はこちらです。

ある配列がある。
その配列に含まれない数で最小の値を求めよ。
最小の値minは0より大きい数とする。

例
var numList = [1, 4, 6, 8, 10]
この場合は2

var numList = [3, 5, 9, 11]
この場合は1

個人的に書いたコードが以下になります。
変数名などがちょっとイケてないのであれですが、、、

// 1から与えられた数字までの配列を作る
// 5 → [1,2,3,4,5]
var untilListFromMaxNumber = function(maxNum){
  var _tmpArray = [];

  for(var i = 1; i <= maxNum; i++){
    _tmpArray.push(i)
  }

  return _tmpArray;
}

// ２つの配列で重複していない数字の配列をつくる
var diffArray = function(arrayFromMaxNum, originalNumList){
  var _tmpArray = []
  for(var i = 1; i <= arrayFromMaxNum.length; i ++){
    if (originalNumList.indexOf(i) === -1) {
      _tmpArray.push(i)
    }
  }

  return _tmpArray;
}


// 当たられた配列
var numList = [1, 3, 5, 7, 8, 9, 13, 16];

console.log('最小値を求める')
console.log('与えられた数値は', numList)

// 最大値を取得
var maxNum = Math.max.apply(null, numList)

console.log('最大値は', maxNum)

var untilList = untilListFromMaxNumber(maxNum)

console.log('最大値までの配列は', untilList)

var filterdArray = diffArray(untilList, numList)

console.log('上記２つの配列の差分は', filterdArray)
console.log('この配列の最小値が最初の配列にない数字の最小値')

var resultNum = Math.min.apply(null, filterdArray)

console.log('最小値は', resultNum)

これをconsoleで実行すると以下の画像のようになります。

これはこれで出来てるのですが、漠然といけてないなあって思っていて、何かいい方法や書き方をいろんな方にご教示いただけないかなぁと思って投稿させて頂きました。

不適切な質問であったらすいません。

よろしくお願いいたします。

Answer 1

模範解答はfor文を利用してこんな感じになるかと思います。

// 当たられた配列
var numList = [1, 3, 5, 7, 8, 9, 13, 16];
var minOf = function(numList) {
  for (var i = 1; true; i++) {
    if (numList.indexOf(i) === -1) {
      return i;
    }
  }
}
console.log(minOf(numList));

---

Lodash.jsを使えば関数型プログラミング的に
もっと問題文をダイレクトにソースコードに書き起こせるようになるかと思いますが、
外部ライブラリを使用してもいいもか…という感じですね。

その視点であれば、イケてないと感じるコードもサラッとイケてる実装に変換できます。
実行パフォーマンスでは上記のfor文ゴリ押しには負けますが、
質問文のロジックをストンと落としたようなコードに変化しかっこいいですね。

このように関数やメソッド、ライブラリを知っていれば勉強すればした分だけ
思いついた内容をダイレクトにソースコードに変換出来るようになります。
基礎になるArray.prototypeも勉強してみてください。

var numList = [1, 3, 5, 7, 8, 9, 13, 16];
var diffList = _.drop(
  Array
  .apply(null, {length: _.max(numList) + 2})
  .map(Number.call, Number)
);
console.log(_.min(_.difference(numList, diffList)));

※比較配列を作っているイディオム的な箇所は、Stack Overflowの記事を参考にしました。

Comments

[MasakazuFukami]

外部ライブラリが使えない状況だったのでlodashなどは一旦考えていませんでした！

そして模範解答的なものありがとうございます！
複雑に考えすぎていました(　；∀；)

Array.prototype見てみます！！！！
ありがとうございます！！！

[miyabi-sun]

余談なのでコメント欄ですが、関数型プログラミングの本場、Haskellでは遅延評価が出来ます。
与えられた配列の+1とは言わず1～無限の配列を作ってしまって、差分をとり、最小の数値だけ返すというロジックも最小の計算量で出来ます。
Haskellに限ってはループ文を使ったやり方と速度的に見ても遜色ありません。