Skip to content

LeetCode: 136-Single Number 解題紀錄

Last Updated on 2022-02-15 by Clay

題目

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

Constraints:

  • 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.

題目給定一組純數字陣列輸入,陣列中只會存在唯一一個不重複的數字,其他的數字都一定會出現兩次。

而題目則規定,你必須在線性時間 O(n) 和常數空間 O(1) 的限制中解開這題。

不過即使使用了時間複雜度為 O(nlogn) 的排序,此時一樣可以通過測試,將來會不會再修改就不知道了。


解題思路

排序法(並未按照題目要求)

一開始,我的第一感是先從小到大排序,接著按照 1、3、5...... 這樣的奇數索引去比對跟自己前一號的數字是否相同。如果找到不同的,比方說 Example 1 排序後的 [1, 2, 2],我們找到了 1 和 0 索引對應的數值不同,則回傳 nums[0]

假設是 Example 2 的情況,nums = [4,1,2,1,2] 會變成 [1, 1, 2, 2, 4],我們走完整個奇數索引也找不到相異值,這時就要直接回傳最後一個數值。


排序法複雜度

由於排序法使用了 n*log(n) 的排序,所以時間複雜度比較高。

Time ComplexityO(nlogn)
Space ComplexityO(1)


排序法 C++ 範例程式碼

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // Sort
        sort(nums.begin(), nums.end());

        // Search
        for (int i=1; i<nums.size(); i+=2) {
            if (nums[i] != nums[i-1]) {
                return nums[i-1];
            }
        }
        
        return nums.back();
    }
};



排序法 Python 範例程式碼

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Sort
        nums.sort()
        
        # Search
        for i in range(1, len(nums), 2):
            if (nums[i] != nums[i-1]): 
                return nums[i-1]
        
        return nums[-1]



XOR

XOR 是一種位元操作的技巧,基本上就是將相異位取 1,同位取 0。

假設我們有 X 和 Y 兩個元素:

XYOutput
000
011
101
110

也就是說,假設我們印出 15 ^ 15^ 是 XOR 的符號而非次方符號)則一定會印出 0,因為每一個數字跟自己的二進制都是完全相同的(我好像講了一件很理所當然的事情......)。

那麼 15 ^ 15 ^ 30 呢?則一定會印出 30

Example 1 的情況如果將整個陣列做 XOR:1 ^ 2 ^ 2 則一定印出 1

Example 2 的情況如果將整個陣列做 XOR:1 ^ 1 ^ 2 ^ 2 ^ 4 則一定會印出 4

因為同樣的數值會自己抵銷掉,剩下的就是沒有重複的值了。


XOR 複雜度

因為只有將陣列遍歷過一次,所以時間複雜度只有 O(n)

Time ComplexityO(n)
Space ComplexityO(1)


XOR C++ 範例程式碼

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // Init
        int ans = 0;

        // Search
        for (int n: nums) {
            ans ^= n;
        }
        
        return ans;
    }
};



XOR Python 範例程式碼

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Init
        ans = 0
        
        # Search
        for n in nums:
            ans ^= n
        
        return ans


References


Read More

Leave a Reply