leetcode解題：(Easy) 136. Single Number

題目：https://leetcode.com/problems/single-number/

描述：找出輸入的陣列中唯一一個沒有重複出現第二次的數字，時間複雜度與空間複雜度的限制分別為O(n)跟O(1)

解題思路(1)：用HashSet紀錄出現過的數字，如果數字重複出現就從set中移除，最後set最後剩下的唯一一個元素就是只出現過一次的數字

程式碼：

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();

        for(int num : nums) {
            if(set.contains(num)) set.remove(num);
            else set.add(num);
        }

        for(int num : set) return num;
        return 0;
    }
}

時間複雜度：O(n)
空間複雜度：O(n)

雖然leetcode有給過，但這個方法的空間複雜度並不符合題目要求，因此下面的才是正確解法

---

解題思路(2)：利用XOR的特性：A^BA=B，將陣列中所有元素進行XOR計算後最後會剩下唯一沒有重複出現的數字

程式碼：

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;

        for(int num : nums) {
            result ^= num;
        }

        return result;
    }
}

時間複雜度：O(n)
空間複雜度：O(1)

tags: leetcode easy map/set