tsanmmmm2000's Tech Blog

Question

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Thinking

直觀一點，我們可以透過Dictionary記錄數字出現與否的方式來求得答案

public class Solution {
    public int SingleNumber(int[] nums) {
        var dic = new Dictionary<int, int>();
        for (var i = 0; i < nums.Length; i++)
        {
            if (dic.ContainsKey(nums[i]))
            {
                dic.Remove(nums[i]);
            }
            else
            {
                dic.Add(nums[i], nums[i]);
            }
        }
        return dic.ElementAt(0).Value;
    }
}

不過題目有提到時間複雜度最好能做到O(n)、空間複雜度O(1)，所以此題其實是考位元運算XOR，其特性是當某數字做了偶數次的XOR，它會回到0，因此最後遺留下來的就會是答案

My C# Solution

public class Solution {
    public int SingleNumber(int[] nums) {
        var result = 0;
        for (var i = 0; i < nums.Length; i++)
        {
            result ^= nums[i];
        }
        return result;
    }
}