372. The Repeated Ticket
A theatre sold n + 1 tickets, each with a seat number between 1 and n. By the pigeonhole principle at least one seat number was sold more than once, and in this problem exactly one seat number is repeated, although it may have been sold more than twice.
Given the array nums of sold seat numbers, return the repeated seat number. You may not modify the array, and you may only use O(1) extra space, so sorting the array or marking visited numbers is not allowed. Aim for O(n log n) time.
Example 1
- Input:
- nums = [3,1,3,4,2]
- Output:
- 3
- Explanation:
The seat number 3 was sold twice.
Example 2
- Input:
- nums = [2,2,2,2]
- Output:
- 2
- Explanation:
Only seat 2 appears, four times.
Constraints
1 ≤ n ≤ 105nums.length == n + 1
1 ≤ nums[i] ≤ n
Exactly one value is repeated (two or more times); every other value appears once.
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 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(1)