You get a vector nums of n + 1 whole numbers. Each number is from 1 to n.
One number appears more than once. Return that number.
Don't change nums. The tests check that it stays the same.
Use only a few extra variables. Don't copy nums, and don't keep an unordered_set of the numbers you have seen.
Why is this a linked list lesson? Think of each index as a node. Then nums[i] is the index of the next node.
Example 1:
Input: nums = [3,5,1,2,4,3] Output: 3 Explanation: 3 appears at index 0 and at index 5. As a linked list, the walk from index 0 goes: 0 -> 3 -> 2 -> 1 -> 5 -> 3 -> 2 -> ... It goes around forever, and the loop starts at 3.
Example 2:
Input: nums = [4,2,4,4,1] Output: 4 Explanation: 4 appears three times. The number 3 does not appear at all.
Example 3:
Input: nums = [1,1] Output: 1 Explanation: Here n is 1, so both numbers must be 1.
Constraints:
- n is from 1 to 100,000.
numshas n + 1 numbers.- Each number is from 1 to n.
- Exactly one number repeats, maybe many times.
- Every other number appears at most once.
Your solution should run in O(n) time with O(1) extra memory.
Start at index 0 and follow the arrows: from index
i, go to index nums[i]. No number is 0, so the walk never comes back to index 0. It has only n other indexes to visit, so it must run into a loop.
Two indexes hold the repeated number, so two arrows lead into it. That is where the loop starts. Find that index as in Linked List Cycle: a slow and a fast pointer meet inside the loop. Then put one pointer back at index 0. Move both one step at a time. They meet where the loop starts.
Each of the two walks takes at most a few times n steps: O(n) time.
Only two indexes are kept: O(1) extra memory.
Keeping an unordered_set of seen numbers also takes O(n) time, but it needs O(n) extra memory. Sorting would change
nums.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
