碎片時間學演算法(3)-只出現一次的數字
給定一個非空整數陣列,除了某個元素只出現一次以外,其餘每個元素均出現兩次。找出那個只出現了一次的元素。
說明:
你的演算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎?
示例 1:
輸入: [2,2,1] 輸出: 1
示例 2:
輸入: [4,1,2,1,2] 輸出: 4
解法1:
首先給出一個最普通的辦法,既不是線性複雜度,又增加了額外空間。那就是藉助於HashMap.
public static int test1(int[] nums) { HashMap<Integer,Integer> hashMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { Integer integer = hashMap.get(nums[i]); hashMap.put(nums[i], (integer == null ? 0 : integer) + 1); } for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) { if (entry.getValue() == 1) { return entry.getKey(); } } return -1; }
這個解題思路是,先將陣列迴圈一遍,陣列的值作為key,出現的次數作為value,之後再遍歷map,找出value為1的。
解法2:
這個解法是滿足題目要求的。線性複雜度,只需遍歷一次,並且沒有增加額外空間。那就是用異或解決。
異或指,進行位運算,相同則結果為0,不同則結果為1。
0010 0100 ^ 0010 0100 = 0000 0000
同時,異或滿足
交換律 : 即a ^ b = b ^ a 結合律:a ^ (b ^ c) = (a ^ b) ^ c 恆等律:a ^ 0 = a 歸零律:a ^ a = 0
所以,根據題目可得,題目滿足於 a ^ b ^ a ^ b ^ c 格式
根據以上定律可得
a ^ b ^ a ^ b ^ c = a ^ a ^ b ^ b ^ c
即可得出
a ^ b ^ a ^ b ^ c = a ^ a ^ b ^ b ^ c = 0 ^ 0 ^ c = 0 ^ c = c
由以上推論可以得出以下程式碼:
public int test(int[] nums){ int num = 0; for (int i = 0 ; i < nums.length ; i++){ num ^= nums[i]; } return num; }
滿足題目要求。