LeetCode - 単一の数字

問題文

整数 nums の空でない配列を指定すると、すべての要素が 1 つを除いて 2 回表示されます.その1つを見つけてください.

ランタイムの複雑さが線形であるソリューションを実装し、一定の余分なスペースのみを使用する必要があります.

https://leetcode.com/problems/single-number から取られた問題の説明.

例 1:

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

例 2:

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

例 3:

Input: nums = [1]
Output: 1

制約:

- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Each element in the array appears twice except for one element which appears only once.

説明

ブルートフォースソリューション

力ずくの解決策は、すべての要素が 1 回出現するかどうかを確認することです. 1 回出現する要素が見つかったら、その要素を返します.上記のアプローチの時間計算量は O(N^2) です.

ハッシュを使用すると、時間の複雑さを O(N) に減らすことができます.配列内のすべての要素をトラバースし、それらをハッシュ テーブルに入れます.配列要素はハッシュ テーブルのキーになり、その値は配列内のその要素の出現回数になります.

このアプローチの C++ スニペットは次のとおりです.

int singleNumber(vector<int>& nums) {
    map<int, int> m;

    for(int i = 0; i < nums.size(); i++) {
        m[nums[i]]++;
    }

    for(auto const & [key, value]: m) {
        if(value == 1) {
            return key;
        }
    }

    return -1;
}

時間の複雑さは O(N) に減少しますが、空間の複雑さは O(N) に増加します.

最適化されたソリューション

単一の int 変数を使用することで、スペースの複雑さを O(1) に減らすことができます.算術 XOR 演算子 ^ を使用できます.オペランドが類似している場合、XOR 演算子は 0 を返します.

3 ^ 1
=> 2

3 ^ 2
=> 0

3 ^ 0
=> 3

配列内のすべての要素は 1 つを除いて 2 回出現するため、すべての重複の XOR は 0 を返します.また、ゼロを含むゼロ以外の数値の XOR は同じ数値を返します.配列を繰り返し処理し、すべての要素に対して XOR を実行する必要があります.

アルゴリズムを確認してみましょう.

- initialize singleNum = 0

- loop for i = 0; i < nums.size(); i++
  - singleNum ^= nums[i]

- return singleNum

C++、Golang、Javascript でのソリューションをチェックしてみましょう.

C++ ソリューション

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int singleNum = 0;

        for(int i = 0; i < nums.size(); i++) {
            singleNum ^= nums[i];
        }

        return singleNum;
    }
};

Golang ソリューション

func singleNumber(nums []int) int {
    singleNum := 0

    for i := 0; i < len(nums); i++ {
        singleNum ^= nums[i]
    }

    return singleNum
}

Javascript ソリューション

var singleNumber = function(nums) {
    let singleNum = 0;

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

    return singleNum;
};

アルゴリズムをドライランして、ソリューションがどのように機能するかを見てみましょう.

Input: nums = [4, 1, 2, 1, 2]

Step 1: singleNum = 0

Step 2: loop for i = 0; i < nums.size()
          0 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[0]
                     = 0 ^ 4
                     = 4

          i++
          i = 1

Step 3: i < nums.size()
          1 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[1]
                     = 4 ^ 1
                     = 5

          i++
          i = 2

Step 4: i < nums.size()
          2 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[2]
                     = 5 ^ 2
                     = 7

          i++
          i = 3

Step 5: i < nums.size()
          3 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[3]
                     = 7 ^ 1
                     = 6

          i++
          i = 4

Step 6: i < nums.size()
          4 < 5
          true

          singleNum ^= nums[i]
                     = singleNum ^ nums[4]
                     = 6 ^ 2
                     = 4

          i++
          i = 5

Step 7: i < nums.size()
          5 < 5
          false

Step 8: return singleNum

So we return the answer as 4.