# LeetCode Easy 136. Single Number
tags: leetcode
問題
アイデア
空でない整数の配列が与えられた時に,1つ以外は2回現れ,その1つは1回のみ現れる.その際の1つだけ現れるものを見つけろという問題です.
アルゴリズムは線形時間に解けないといけず,追加の記憶領域を使わずに実装するというのも目標です.
空間計算量の効率が悪くても良いなら,連想配列を使い,整数と登場回数を対応させます.
空間計算量の効率を最大にする場合はひと工夫必要です.
解法1(連想配列)
std::unorderd_map
でkeyが配列の整数,valueに登場回数を保存します.
配列を走査して,整数をkeyとするvalueをインクリメントします.
そして,最後にvalueが1
となるときのkeyを返します.
計算量
配列の大きさを$N$とします.
- 時間計算量
- $O(N)$
- 空間計算量
- $O(N)$
C++
class Solution { public: int singleNumber(vector<int>& nums) { map<int, int> mp; for (auto& num : nums) mp[num]++; for (auto& num : nums) if (mp[num] == 1) return num; return -1; } };
class Solution { public: int singleNumber(vector<int>& nums) { map<int, int> mp; for (auto& num : nums) mp[num]++; for (auto& ele : mp) if (ele.second == 1) return ele.first; return -1; } };
解法2(XOR)
XOR
を使います.XOR
の以下の特徴を使います
A XOR A = 0
A XOR B = B XOR A
1つ目の特徴を使い,2度現れた整数同士に作用させると計算結果は0となります.
2つ目の特徴を使い,配列の順番は依存せず全ての配列の整数に作用させると計算結果は1回しか登場しない整数となります.
計算量
- 時間計算量
- $O(N)$
- 空間計算量
- $O(1)$
C++
class Solution { public: int singleNumber(vector<int>& nums) { int res; for (auto& num : nums) res ^= num; return res; } };