280. Two Lone Values
A turnstile counter records the badge number of every person who walks through a gate. Each badge holder passes through twice, once in and once out, except for two people who only entered and never left; their two badge numbers are different from each other. Badge numbers are arbitrary 32-bit signed integers and the log is unordered.
Given the array nums, return an array of length 2 holding the two badge numbers that appear only once, sorted in ascending order. The input is guaranteed to have exactly two values that appear once, while every other value appears exactly twice.
Counting each value against the whole array takes quadratic time, which is wasteful for long logs. Aim for O(n) time and O(1) extra space.
Example 1
- Input:
- nums = [14,-3,14,60,9,9]
- Output:
- [-3,60]
- Explanation:
Only -3 and 60 appear once; all others appear twice.
Example 2
- Input:
- nums = [-2147483648,8,2147483647,8]
- Output:
- [-2147483648,2147483647]
- Explanation:
Only -2147483648 and 2147483647 appear once; all others appear twice.
Example 3
- Input:
- nums = [41,0,41,6]
- Output:
- [0,6]
- Explanation:
Only 0 and 6 appear once; all others appear twice.
Constraints
2 ≤ nums.length ≤ 4000
-231 ≤ nums[i] ≤ 231 - 1
Exactly two distinct values appear once; every other value appears exactly twice.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)