You are given a sorted list of integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution for the main problem must run in O(log n) time and O(1) extra space.
Follow up: Solve the same problem in O(log n) time and O(1) extra space when every element other than the single element appears exactly three times.
Methods
int singleNonDuplicate(List<Integer> nums)
nums is sorted in non-decreasing order- Exactly one value appears once
- Every other value appears exactly twice
- The size of
nums is odd
int singleNonTriplet(List<Integer> nums)
nums is sorted in non-decreasing order- Exactly one value appears once
- Every other value appears exactly three times
- The size of
nums is of the form 3k + 1
Constraints
1 ≤ nums.size() ≤ 100,000-10^8 ≤ nums.get(i) ≤ 10^8nums is sorted in non-decreasing order- For the main problem, every value except one appears exactly twice
- For the follow-up problem, every value except one appears exactly three times
Notes
- The input is guaranteed to contain exactly one valid answer.
- You must not use extra space proportional to the input size.
- The main problem requires
O(log n) time and O(1) extra space.
- The follow-up asks for the same complexity when repeated elements appear three times instead of twice.
Examples
Example 1
Method: singleNonDuplicate(nums = [1, 1, 2, 3, 3, 4, 4, 8, 8])
Output: 2
Explanation: The value 2 appears exactly once, while every other value appears exactly twice.
Example 2
Method: singleNonDuplicate(nums = [3, 3, 7, 7, 10, 11, 11])
Output: 10
Explanation: The value 10 is the only element that appears once.
Example 3
Method: singleNonDuplicate(nums = [0])
Output: 0
Explanation: The list contains only one element, so that element is the answer.
Example 4
Method: singleNonTriplet(nums = [1, 1, 1, 2, 3, 3, 3])
Output: 2
Explanation: The value 2 appears once, while every other value appears exactly three times.
Example 5
Method: singleNonTriplet(nums = [4, 4, 4, 6, 6, 6, 9, 10, 10, 10])
Output: 9
Explanation: The value 9 is the only element that appears once.