207. Fewest Swaps to Order
A shelf holds n books numbered from 0 to n - 1, each number appearing exactly once, but the books are in a jumbled order given by nums. The librarian wants them in increasing order, 0, 1, 2, ..., n - 1.
In one move the librarian may pick any two positions on the shelf, not necessarily next to each other, and swap the books there. Return the smallest number of moves needed to put the shelf in order. If it is already in order, the answer is 0.
Example 1
- Input:
- nums = [2,0,1]
- Output:
- 2
- Explanation:
Position 0 should hold 0, which sits at position 1; the books 2, 0, 1 form one loop of length 3, which needs 2 swaps.
Example 2
- Input:
- nums = [0,1,2,3]
- Output:
- 0
- Explanation:
The shelf is already in order.
Example 3
- Input:
- nums = [1,0,3,2]
- Output:
- 2
- Explanation:
Two independent pairs are out of place; each needs one swap, so 2.
Constraints
1 ≤ nums.length ≤ 105nums contains each integer from 0 to nums.length - 1 exactly 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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)