Single Number III
Given an integer array nums, where exactly two elements appear only once and all other elements appear exactly twice, find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1, 2, 1, 3, 2, 5]
Output: [3, 5]
Explanation: [5, 3] is also a valid answer.
Example 2:
Input: nums = [-1, 0]
Output: [-1, 0]
Example 3:
Input: nums = [0, 1]
Output: [1, 0]
Constraints:
2 ≤ nums.length ≤ 30,000
-231 ≤ nums[i] ≤ 231 - 1
Each integer in nums will appear twice, except for two integers that will appear once.
Approach 1: Hashmap
Build a hashmap : element -> its frequency. Return only the elements with the frequency equal to 1.
class Solution {
public int[] singleNumber(int[] nums) {
Map hashmap = new HashMap();
for (int n : nums)
hashmap.put(n, hashmap.getOrDefault(n, 0) + 1);
int[] output = new int[2];
int idx = 0;
for (Map.Entry item : hashmap.entrySet())
if (item.getValue() == 1) output[idx++] = item.getKey();
return output;
}
}
Complexity Analysis
Time complexity : O(N) to iterate over the input array. Space complexity : O(N) to keep the hashmap of N elements.
