Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 136. Single Number

發表於 分類於 ， ， Disqus：
如何找出單獨的那個數呢?

前言

　　這題目的邏輯是找出陣列中只出現過一次的元素，直覺是用一層 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.

範例

1
2
Input: nums = [2,2,1]
Output: 1
1
2
Input: nums = [4,1,2,1,2]
Output: 4
1
2
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

JAVA 初階實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
    }
}

JAVA 進階實現

筆者還在學習中，參考了討論區裡網友的解法，這個技巧比較特別，有點偏向數學題目。

這裡會使用到邏輯運算 XOR，位元運算的特性，數學的交換律。

了解以下說明，步驟會很明瞭，運用數學交換律來排序後，新的排序會從小排到大而且一樣的整數會倆倆相鄰，然後已知的兩整數用邏輯運算後相不相同表示 0 或 1，得出最後無法被削除的整數是 4。

1
2
3
4
5
6
7
8
9
邏輯運算 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
1
2
3
4
5
6
7
8
9
10
11
12
位元運算的特性

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做
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
如何使用在題目

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
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int singleNumber(int[] nums) {

        int xor = 0;

        for (int i : nums) {
            xor ^= i; // xor = xor ^ i
        }

        return xor;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

參考資料

https://www.youtube.com/watch?v=Hy1hE0HBR3U