Programming
Leetcode-136. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
<解題>
- 利用了 XOR 運算的幾個性質：
XOR 運算具有交換律：a^b = b^a XOR 運算具有結合律：(a^b)^c = a^(b^c) 對於任何數字 a，a^a = 0，即同一數字連續進行 XOR 運算會得到 0 對於任何數字 a，a^0 = a，即任何數字與 0 進行 XOR 運算結果等於它本身
-
先把數字想成二進位：//nums = [4,1,2,1,2] 2 → 010 4 → 100 1 → 001
-
相同的會是0，不同的會是1 0 xor 0 = 0 0 xor 1 = 1 1 xor 0 = 1 1 xor 1 = 0
-
將所有重複出現的元素兩兩抵消，留下的只有只出現一次的元素，按照XOR的邏輯：//nums = [4,1,2,1,2]
- 100 = 000 ^ 100 (0^4)
- 101 = 100 ^ 001 (4^1)
- 111 = 101 ^ 010 (5^2)
- 110 = 111 ^ 001 (7^1)
- 100 = 110 ^ 010 (6^2) ->最後result回傳4
class Solution {
public int singleNumber(int[] nums) {
int result=0;
for(int i=0; i<nums.length; i++) {
result = result^nums[i];
}
return result;
}
}
Time: O(N) Space: O(1)
<解題>方法二
map.put(num, map.getOrDefault(num, 0) + 1)->map.getOrDefault(num, 0) 會取得鍵 num 對應的值，如果鍵不存在，則返回默認值 0。接著再將值加 1，表示該元素出現次數加 1。
class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int num : nums){
if( !map.containsKey(num)){
map.put(num , 1);
} else {
map.put(num , 2);
}
}
for (int num : nums){
if ( map.get(num)==1) return num;
}
return -1;
}
}
Time: O(N) Space: O(N)
class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1); //map.getOrDefault(num, 0) 會取得鍵 num 對應的值，如果鍵不存在，則返回默認值 0。接著再將值加 1，表示該元素出現次數加 1。
}
for (int num : nums){
if ( map.get(num)==1) return num;
}
return -1;
}
}