Given an array arr[] containing 2*n + 2 positive numbers, out of which 2*n numbers exist in pairs whereas only two number occur exactly once and are distinct. Find the other two numbers. Return the answer in increasing order.
Examples:
Input: arr[] = [1, 2, 3, 2, 1, 4] Output: [3, 4] Explanation: 3 and 4 occur exactly once.
Input: arr[] = [2, 1, 3, 2] Output: [1, 3] Explanation: 1 and 3 occur exactly once.
Input: arr[] = [2, 1, 3, 3] Output: [1, 2] Explanation: 1 and 2 occur exactly once.
Constraints:
2 ≤ arr.size() ≤ 106
1 ≤ arr[i] ≤ 5 * 106
arr.size() is even
Approach 01:
-
C++
-
Python
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> singleNum(const vector<int>& nums) {
unordered_map<int,int> frequencyMap;
for (int num : nums) {
++frequencyMap[num];
}
vector<int> uniqueNumbers;
for (const auto& entry : frequencyMap) {
int num = entry.first;
int freq = entry.second;
if (freq == 1) {
uniqueNumbers.push_back(num);
}
}
sort(uniqueNumbers.begin(), uniqueNumbers.end());
return uniqueNumbers;
}
};
Time Complexity:
- Building Frequency Map:Iterate through
numsonce, updating the map in \(O(1)\) average time per operation → \(O(n)\). - Collecting Unique Elements:Iterate through the map (at most \(n\) entries) → \(O(n)\).
- Sorting Result:Sort the unique numbers array of size \(k \le n\), taking \(O(k \log k)\). In the worst case \(k = n\), so \(O(n \log n)\).
- Total Time Complexity:\(O(n \log n)\).
Space Complexity:
- Frequency Map:Stores up to \(n\) entries → \(O(n)\).
- Result Array:Stores up to \(n\) unique numbers → \(O(n)\).
- Total Space Complexity:\(O(n)\).
import collections
from typing import List
class Solution:
def singleNum(self, nums: List[int]) -> List[int]:
frequency = collections.Counter(nums)
uniqueNumbers = [num for num, count in frequency.items() if count == 1]
uniqueNumbers.sort()
return uniqueNumbers
Time Complexity:
- Building Counter:
Iterate through
numsonce, updating counts in \(O(1)\) average time per update → \(O(n)\). - Filtering Unique Elements:
Iterate through at most \(n\) map entries → \(O(n)\).
- Sorting Result:
Sort the list of unique numbers of length \(k \le n\), which takes \(O(k \log k)\). In the worst case \(k = n\), so \(O(n \log n)\).
- Total Time Complexity:
\(O(n \log n)\).
Space Complexity:
- Counter Storage:
Stores up to \(n\) counts → \(O(n)\).
- Result List:
Stores up to \(n\) unique numbers → \(O(n)\).
- Total Space Complexity:
\(O(n)\).