古代のアルゴリズムの魔法、または LeetCode からの興味深い一連のタスクの解決

少し前に、Web サイト leetcode.com で一連の面白いタスクを見つけました。タスク自体はそれほど難しくありませんが、その解決策は非常に興味深いものです。また、この種の問題は大手企業の面接でもよく出てくるので、その解決方法を知っておくことは非常に有益です。

最初のタスクは 136 です。単一の数字 (簡単)

1 つを除いてすべての要素が 2 回出現する空ではない整数の配列を指定すると、ペアのない要素を見つける必要があります。 O(n) 時間の計算量と一定の追加メモリを使用して問題を解決します。

例 1:

入力: 数値 = [1、3、3、2、6、2、1]

出力: 6

例 2:

入力: 数値 = [12, 1, 1, 7, 1, 12, 1]

出力: 7

例 3:

入力: 数値 = [6]

出力: 6

オペランドが異なる場合にのみ 1 を生成する XOR 関数のプロパティを利用します。配列のすべての要素を調べてビットごとの XOR を実行することにより、すべての同一のビット値をゼロにします。その結果、望ましい結果が残ります。

以下は短い Python3 ソリューション コードです。

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

整数が占有するのと同じ量の追加メモリのみを使用し、指定された配列を 1 回通過するだけで解を求めるため、複雑さは O(n) になります。これは簡潔でエレガントなソリューションです。

2 番目の問題は 137. シングルナンバー II (中難易度)

すべての要素が 1 つを除いて 3 回出現し、1 つの要素のみが 1 回出現する空ではない整数の配列を考えると、この一意の要素を見つける必要があります。 O(n) 時間の計算量と一定の追加メモリを使用して問題を解決します。

例 1:

入力: 数値 = [3, 1, 3, 3]

出力: 1

例 2:

入力: 数値 = [12, 1, 1, 5, 1, 12, 12]

出力: 5

例 3:

入力: 数値 = [6]

出力: 6

残念ながら、この場合、必要な位置にあるペアのビットをゼロに変えることができないため、前のトリックを使用することはできません。指定された配列を前のタスクの形式に変換し、同様の方法で解決したくなるでしょう。

このように推論すると、配列を走査している間に数値 N にすでに 2 回 (または 3 回) 遭遇していることがわかっていれば、取得している合計に N との XOR を追加できることが容易にわかります。これにより、この数値との最終的な XOR が偶数になり、最終的な合計からその数値が削除され、残ったものが答えとなります。

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

残念ながら、この解決策では最大 (len(nums)-1)/3 のメモリが必要になりますが、これは一定の消費とはみなされないため、別の解決策を探す必要があります。

アプローチを変えてみましょう。

先ほどは XOR (加算法 2 を表す) を使用しました。加算法 3 を実装していれば、前の例のトリックを簡単に適用できたはずです。

初めて答えに遭遇したときに答えに数値を入力し、2 回目でそれをアキュムレータに入れ、3 回目で答えとアキュムレータの両方をゼロにすることができれば、1 回のパススルーで問題を解決するのに役立ちます。追加のメモリ消費量が 2 つの整数に正確に等しいリストは、タスクの要件を満たします。

そこで、もう少しビット単位のマジックを適用してみましょう。

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

このようにして、すべての 3 倍の数字がゼロに設定され、1 回だけ出現する数字だけが残ります。

3番目のタスクは260です。シングルナンバーIII（中難易度）

1 回しか出現しない 2 つの要素を除いて、すべての要素が 2 回出現する空でない整数の配列を考えると、これらの一意の要素を見つける必要があります。目標は、一定の追加メモリを使用して O(n) 時間の計算量で問題を解決することであり、固有の要素の順序は重要ではありません。

例 1:

入力: 数値 = [1、2、1、3、2、5]

出力: [3、5]

例 2:

入力: 数値 = [1, -2]

出力: [-2、1]

明らかに、最初のタスクを解決したときと同様に、XOR 演算を使用してすべてのペアの数値を簡単に削除できます。このタスクの複雑さは、一意の数値を識別することにあり、その後、2 番目の数値は XOR 合計と XOR 演算することで簡単に計算できます。

これを達成するには、これらの一意の数値の間で異なるビットを見つけるだけで済みます。次に、配列を再度繰り返し、XOR 合計を実行し、結果を 2 つのグループ (このビットが設定されている数値と 0 の数値) に分割します。その結果、必要な一意の要素が得られます。

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

配列を 2 回繰り返す必要があるにもかかわらず、複雑さは O(n) のままで、メモリ消費量は整数 2 つだけです。

注意: Python の int は他の言語の int とまったく同じではないという事実にもかかわらず、そのサイズを定数として考慮します。