Single Number III Problem


Description

LeetCode Problem 260.

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write analgorithm that runs in linear runtime complexity and usesonly constant extra space.

Example 1:

1
2
3
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

1
2
Input: nums = [-1,0]
Output: [-1,0]

Example 3:

1
2
Input: nums = [0,1]
Output: [1,0]

Constraints:

  • 2 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Each integer in nums will appear twice, only two integers will appear once.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> singleNumber(vector<int> &nums) {
        unordered_map<int, int> freq;

        for (auto &num: nums) ++freq[num];
        
        vector<int> ans;

        for (auto &[x, f]: freq)
            if (f == 1) {
                ans.push_back(x);
                if (ans.size() == 2)
                    return ans;
            }
        return ans;
    }
};




Related Posts

Bulb Switcher II Problem

LeetCode 672. There is a room with n bulbs labeled...

Binary Number With Alternating Bits Problem

LeetCode 693. Given a positive integer, check whether it has...

Total Hamming Distance Problem

LeetCode 477. The Hamming distance between two integers is the...

Number Complement Problem

LeetCode 476. The complement of an integer is the integer...

Hamming Distance Problem

LeetCode 461. The Hamming distance between two integers is the...

Convert A Number To Hexadecimal Problem

LeetCode 405. Given an integer num, return a string representing...