Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
<Solution>Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
這題本身不難,但是因為要求 O(N) 以及不能使用額外的空間,很難直接想到解法
其實這題是在考 XOR 的觀念
S 是要找的答案
N1 ^ N1 ^ N2 ^ N2 ..... ^ Nx ^ Nx ^ S
= (N1 ^ N1) ^ ( N2 ^ N2) .... ^ (Nx ^ Nx) ^ S
= 0 ^ 0 .... ^ 0 ^ S
= S
所以只要用 XOR 歷遍一次,答案就出來了
code 如下(參考資料)
c++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int singleNumber(vector<int>& nums) { | |
int ans = 0; | |
for(const auto &n : nums) { | |
ans ^= n; | |
} | |
return ans; | |
} | |
}; |
Kotlin
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
fun singleNumber(nums: IntArray): Int { | |
var ans = 0 | |
for(n in nums) { | |
ans = ans xor n | |
} | |
return ans | |
} | |
} |
沒有留言:
張貼留言