這題目的邏輯是找出陣列中只出現過一次的元素,直覺是用一層 for 迴圈遍歷整個陣列後,使用 HashMap 來儲存元素跟出現的次數,最後再遍歷 Map 出結果,不過這樣同時會用到兩個 for 迴圈,時間複雜度推估會達到 O(N^2)
,另外討論區有比較高階的算法只需用到一個迴圈,時間複雜度可達 O(n)
,這裡有 JAVA 和 Python 的寫法。
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.
給定一個非空的整數陣列叫 nums ,每一個元素都會出現兩次除了一個以外。找到那個單獨的 整數。
你必須實現一種方案是線性的運作時間,而且只能使用常數的記憶體空間。
題目連結:https://leetcode.com/problems/single-number/
1 <= nums.length <= 3 * 104
3 * 104 <= nums[i] <= 3 * 104
Each element in the array appears twice except for one element which appears only once.
Input: nums = [2,2,1]
Output: 1
Input: nums = [4,1,2,1,2]
Output: 4
Input: nums = [1]
Output: 1
這邊第一個直覺是用迴圈把所有的整數全部取出來後,依依放在 Map 裡當 Key,然後把每個整數所出現的次數記錄在 Map 裡當 Value,最後遍歷這個 Map 取出 Value 小於 2 的 Key,因為小於 2 就代表陣列中只出現過一次,這個就是我們要的整數了!
int num: nums
遍歷陣列,把出現的元素記錄到 Map- 判斷有無這個元素
- 沒有元素:放進 Map,元素為 Key、整數為 Value
- 有元素:當前的元素的整數 Value +1
- 遍歷 Map 判斷裡面的 Key 的 Value < 2
- 就回傳 Key
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
Map<Integer, Integer> isMap = new HashMap<Integer, Integer>();
// foreach 寫法,類型 int 遍歷後把 nums 裡的每個值丟進 num
for (int num: nums){
// 判斷有無這個元素
if(!isMap.containsKey(num)) {
isMap.put(num, 1); // 放進 Map,元素為 Key、整數為 Value
}else {
isMap.put(num, isMap.get(num)+1); // 當前的元素的整數 Value +1
}
}
// 遍歷 Map 判斷裡面的元素的整數 Value == 1
for (Integer key: isMap.keySet()){ // 取得 Key
// 遍歷 Map 判斷裡面的 Key 的 Value < 2
if(isMap.get(key) < 2){
return result = key; // 就回傳 Key
}
}
return result;
}
}
筆者還在學習中,參考了討論區裡網友的解法,這個技巧比較特別,有點偏向數學題目。
這裡會使用到邏輯運算 XOR,位元運算的特性,數學的交換律。
了解以下說明,步驟會很明瞭,運用數學交換律來排序後,新的排序會從小排到大而且一樣的整數會倆倆相鄰,然後已知的兩整數用邏輯運算後相不相同表示 0 或 1,得出最後無法被削除的整數是4。
邏輯運算 XOR
將倆正整數都轉成 binay 後再進行比較,那雙方的 binay 是一樣的話為 0,不一樣的話為 1。(覺得複雜難理解的話可看下方算式)
每個位元會分開算
int 4 => binay 00000000 00000000 00000000 00000100
int 1 => binay 00000000 00000000 00000000 00000001
---------------------------------------------------------
00000000 00000000 00000000 00000101 => 5
所以 4 ^ 1 = 5
位元運算的特性
A^A => if A = 0, 0^0 => 0
if A = 1, 1^1 => 0
A^0 => if A = 0, 0^0 => 0
if A = 1, 1^0 => 1
A^0 => A (得出1也就是A)
A^B => B^A (交換律意思是相加時可以互相顛倒: A+B => B+A)
最終得到一個現象,自己跟自己做=0,任何人跟0做=任何人,A跟B做=B跟A做
如何使用在題目
int[] nums = {2, 2, 1}
xor = 2^2^1
說明:
1) 2^2 自己跟自己做 => 0 (任何自己跟自己做都是等於0)
2) 0^1 0再跟1做 => 1^0做 (注意這裡不是得到A^0)
3) 1^0 1跟0做 => 1
結果答案得出 xor = 1
int[] nums = {4, 1, 2, 1, 2}
做排序 (因為交換律的特性所以都是相等的,是數學原理排序的不是電腦排的)
4^1^2^1^2 =>
1^4^2^1^2 =>
1^4^1^2^2 =>
1^1^4^2^2 =>
1^1^2^4^2 =>
1^1^2^2^4 (最終)
題目規定,每個整數會出現2次,排序完後整數會倆倆相鄰,所以算出來一樣的會變0
1^1 => 0
2^2 => 0
最後會變成 0^0^4
0的部分全部都會消掉,所以最後答案剩下 4
class Solution {
public int singleNumber(int[] nums) {
int xor = 0;
for (int i : nums) {
xor ^= i; // xor = xor ^ i
}
return xor;
}
}
使用了和 Java 一樣的邏輯執行,換成 Python 的寫法。
class Solution:
def singleNumber(self, nums: [int], result: int) -> int:
dicList = {}
for i in nums:
if i not in dicList: # 如果當前 Key 不在字典裡
dicList[i]=1 # 把 Key 和 Value 添加進去
else:
dicList[i] = dicList[i]+1 # 如果 Key 存在的話 value + 1
for i in dicList:
if dicList[i] == 1: # 如果當前 Key 的 value = 1
return i
return
Language | Runtime | Memory |
---|---|---|
Java | 14ms | 43.6MB |
Python | 163ms | 19.4MB |
(新手上路,如有錯誤請友善告知,感謝)
Blog
https://chris81051.github.io/2023/04/28/LeetCode-136-Single-Number-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論
https://www.youtube.com/watch?v=Hy1hE0HBR3U