LeetCode 瞑想: 欠落番号

この問題の説明から始めましょう:

範囲 [0, n] 内の n 個の個別の数値を含む配列 nums を指定すると、配列に欠落している範囲内の唯一の数値を返します。

例:

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

または:

Input: nums = [0, 1]
Output: 2

Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0, 2]. 2 is the missing number in the range since it does not appear in nums.

または:

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0, 9]. 8 is the missing number in the range since it does not appear in nums.

また、すべての num の数値は 一意であるとも述べられています。

---

これを解決する簡単な方法の 1 つは、範囲の合計を取得し、指定された配列の合計を減算することです。残ったものが不足番号となります。

次のように、reduce を使用して数値を合計することができます。

function missingNumber(nums: number[]): number {
  return Array.from({ 
    length: nums.length + 1 
  }, (_, idx) => idx).reduce((acc, item) => acc + item, 0) 
  - nums.reduce((acc, item) => acc + item, 0);
}

まず、0 から nums.length 1 までの値を持つ配列を作成し、その合計を取得し、そこから nums の合計を減算します。

ただし、時間と空間の複雑さは $O(n)$O(n) このソリューションでは、範囲の配列を作成します。

ビット操作を使用すると、より (ストレージ面) 効率的なソリューションが得られます。
実際、XOR 演算を使用するとこれに役立ちます。

覚えておくと、両方のビットが異なる場合、つまり、一方が 0、もう一方が 1 の場合、XOR の結果は 1 になります。
数値をそれ自体と XOR すると、すべてのビットが同じであるため、結果は 0 になります。

たとえば、2 進数の 3 は 11 で、11 ^ 11 を実行すると、結果は 0 になります。

const n = 3;
const result = n ^ n; // 0

言い換えると、数値とそれ自体の XOR 演算の結果は 0 になります。

配列内の各数値とインデックスを XOR すると、最終的にはすべてがキャンセルされ (結果は 0)、欠落した数値だけが残ります。

すべての数値がそのインデックスにあるわけではないと思うかもしれません。たとえば、nums が [3, 0, 1] の場合、3 には関連付けられる「インデックス 3」さえないのは明らかです!

そのためには、結果を nums.length に初期化することから始めます。ここで、欠落している数値が nums.length に等しい場合でも、そのエッジ ケースを処理します。

let result = nums.length;

また、XOR は可換かつ結合的です。そのため、どのインデックスに数値が現れるか (または上の例のように数値が存在しない) は重要ではありません。それらは最終的には相殺されます。

for ループを使用すると、ビットごとの XOR 代入演算子を使用して XOR を実行できます。

for (let i = 0; i < nums.length; i++) {
  result ^= i ^ nums[i];
}

そして、最終結果は欠番です。ソリューション全体は次のようになります:

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

時間と空間の複雑さ

時間の複雑さが再び $O(n)$O(n) 配列内の各数値を反復処理すると、空間の複雑さは次のようになります。 $O(1)$O(1) 入力サイズの増加に伴って増大する追加のストレージが必要ないためです。

---

次に、シリーズ全体の最後の問題、2 つの整数の合計を見ていきます。それまで、コーディングを楽しんでください。

以上がLeetCode 瞑想: 欠落番号の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。