1. 題目
1.1 英文題目
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.
1.2 中文題目
給定一個非空整數陣列，除了某個元素只出現一次以外，其余每個元素均出現兩次，找出那個只出現了一次的元素，
說明：
你的演算法應該具有線性時間復雜度， 你可以不使用額外空間來實作嗎？
1.3輸入輸出
| 輸入 | 輸出 |
|---|---|
| nums = [2,2,1] | 4 |
| nums = [4,1,2,1,2] | 4 |
| nums = [1] | 1 |
1.4 約束條件
- 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.
2. 分析
這一題我的第一反應是暴力搜索，先構建一個臨時陣列存盤已遍歷元素，若新遍歷元素與之前重復，則不是目標值，從臨時陣列中洗掉；否則加入，遍歷到最后，臨時陣列內只剩余目標值，代碼如下：
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> temp;
vector<int>::iterator iter;
for (int i = 0; i < nums.size(); i++)
{
iter = find(temp.begin(), temp.end(), nums[i]);
if (iter != temp.end()) //找到了，重復元素
temp.erase(iter);
else
temp.push_back(nums[i]);
}
return temp[0];
}
};
之后又看了下一些其他大神們的寫法，讓人直呼妙哉！其中一種是利用set集合不含重復元素的性質，通過將陣列轉為集合，之后用集合元素和的2倍減去原陣列所有元素的和，就是結果，代碼如下：
class Solution {
public:
int singleNumber(vector<int>& nums) {
set<int> setNums(nums.begin(), nums.end());
int sum = accumulate(nums.begin(), nums.end(), 0);
int setSum = accumulate(setNums.begin(), setNums.end(), 0);
return 2 * setSum - sum;
}
};
上面這種演算法在時間和空間消耗上并不是太好，但是這種想法不錯，另外還有一種做法是利用異或的性質，假設所有的陣列為：abcbcda,則
a ^ b ^ c ^ b ^ c ^ d ^ a
= a ^ a ^ b ^ b ^ c ^ c ^ d
= 0 ^ 0 ^ 0 ^ d
= d，
代碼如下：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (auto num : nums)
result ^= num;
return result;
}
};
3. 補充知識
（1）vector
a. 查找vector中的某一個元素
可以利用algorithm頭檔案中find()，用法為：
vector<A>::iterator iter = std::find(vec.begin(), vec.end(), findNum);
b.vector刪減元素
- push_back()尾部添加元素
- pop_back()尾部洗掉元素
- erase(num)洗掉指定元素或指定迭代器位置元素
c.vector與set互轉
- vector轉set:
set<int> st(v.begin(), v.end());//在建構式中可以直接實作vector轉set - set轉vector:
v.assign(st.begin(), st.end());
(2) 異或
a.異或的特性：
- 恒定律：A ^ 0 = A
- 歸零率：A ^ A = 0
- 交換律：A ^ B = B ^ A
- 結合律：(A ^ B) ^ C = A ^ (B ^ C)
b.用途
異或可以快速比較兩個值是否相等 a ^ b == 0，效率非常高，比 a - b == 0 高很多，
異或還能在不定義臨時變數的情況下，交換兩個值（經典題目）
a = a ^ b
b = a ^ b // a ^ b ^ b = a ^ 0 = a
a = a ^ b // a ^ b ^ a = b ^ 0 = b
參考：https://www.jianshu.com/p/e3442ed3d874
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/289046.html
標籤：C++
上一篇：Leetcode No.122 Best Time to Buy and Sell Stock II Easy(c++實作）
下一篇：你檔案亂碼了么