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 Complexity | O(nlogn) |
| Space Complexity | O(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 兩個元素：
| X | Y | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
也就是說，假設我們印出 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 Complexity | O(n) |
| Space Complexity | O(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