【LeetCode】#136 Single Number(C#)

● 問題

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?

● 思考點

在這陣列裡的數字都是成雙成對的,只有一個數字是出現一次的,用最好的計算時間找出該數字。
我一開始想到的是List或Dictionary方式來做,應該會採取Dictionary方式過濾。
找些資料後發現這題最好的方法是用XOR,也就是說重覆數字會變0,最後結果為出現一次的數字。

● Solution

【Dictionary】

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

【XOR】

public class Solution {
    public int SingleNumber(int[] nums) {
        
        var result = 0;
        
        for (var i = 0; i < nums.Length; i++)
        {
            //XOR重覆數字為0
            result ^= nums[i];
        }
        
        return result;
    }
}