Leetcode 136. Single Number

Single Number :

題目給定一組純數字陣列輸入，陣列中只會存在唯一一個不重複的數字，其他的數字都一定會出現兩次。題目規定必須在線性時間 O(n) 和常數空間 O(1) 的限制下解開這題。

目錄

時間複雜度: O(n)

空間複雜度: O(1)

Python

方法一 :

首先排序nums，之後迴圈去判斷相鄰兩數字是否相等，如果不相等則回傳前一個數字，如果數字都一樣，回傳值。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(1,len(nums),2):    #2個間距迴圈
            if(nums[i]!=nums[i-1]):       #相鄰兩數字不相等
                return nums[i-1]          #回傳前一個數字
        return nums[-1]                   #如果數字都一樣，回傳值

方法二:

參考網路解法，用XOR的方式把重複的數字給刪除(重複兩次的數字互相做XOR後會變成0)

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

C++

首先我們對數組nums進行排序，使得相同的數字都排在一起。
然後我們遍歷排序後的數組，每次跳兩個數字，如果相鄰的兩個數字不相同，則返回第一個數字。
如果沒有找到不同的數字，說明最後一個數字出現了一次，返回它即可。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 1; i += 2) {
            if(nums[i] != nums[i+1]) {
                return nums[i];
            }
        }
        return nums.back();
    }
};

相關