[leetcode]問題解答と解説。217. Contains Duplicate [JavaScript]

皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます

私はある決意をして今臨んでいます。
モチベーションを保つためだけにこれをやっています。

では今日のleetCode。
「217. Contains Duplicate」の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。

※下にある自分のコードは自分で設けた制限時間内に書けたところまです。

これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。

217. Contains Duplicate ルール

ざっくり和訳

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

整数配列 nums が与えられたとき、いずれかの値が配列中に少なくとも2回出現すれば真を返し、 すべての要素が異なる場合は偽を返す。

Example 1:

Input: nums = [1,2,3,1]
Output: true
Example 2:

Input: nums = [1,2,3,4]
Output: false
Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

217. Contains Duplicate 問題ページ

217. Contains Duplicate

217. Contains Duplicate

my code is time over.

function containsDuplicate(nums: number[]): boolean {
    const length = nums.length
    return length !== new Set([...nums]).size
};

これは一発合格

217. Contains Duplicate。discussの中の一つの解答例

数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれないですね

JavaScriptでfilterされている、discussはこちらから

217. Contains Duplicate

setとobjectの解決方法の比較について
少ない要素ならsetの方が速いが、
10,000以上あるとobjectの方が速いと伝えている

ここに投稿された多くのJavascriptのソリューションは、Setsを使用した1行の式を使用しており、それは確かに問題を解決するエレガントな方法です。しかし、LeetCodeによると、オブジェクト（基本的にはハッシュテーブル）を使用する私の解決策よりも速いので、少し驚きました。オブジェクトを使うことの利点は、重複を検出した場合に早期にリターンできることです。一方、Setsの場合は、重複があるかどうかを判断する前に配列全体をSetに変換する必要があります。

そこで、少し試してみたところ、小さな配列であればSetsを使った方が速いことがわかりました。大きな配列の場合は、たとえ重複がなく配列全体を調べる必要があっても、オブジェクトを使用した方が圧倒的に速くなります。私の場合は、配列の要素数が10,000程度でクロスオーバーしています。以下はテストコードです（2016年のMacbook ProでNodeで実行、結果は異なる場合があります）。

1

function objectSolution(nums) {
  let testObj = {};
  for (var i = 0; i < nums.length; i++) {
    let aNum = nums[i];
    if (testObj[aNum]) {
      return true;
    } else {
      testObj[aNum] = true;
    }
  }

  return false;
}

217. Contains Duplicateをやってみて感想

解けるかどうかではなく、解けて更にパフォーマンスがいい書き方
を目指そう

カテゴリー leetCode