#2717
Semi-Ordered Permutation
pupil · 350 · lc easy +23 · verified · 64.1% accepted · 228 likes · top 67%
Description
You are given a 0-indexed permutation nums of n distinct integers. A permutation is semi-ordered when nums[0] == 1 and nums[n-1] == n. Use adjacent swaps to reach a semi-ordered state. Return the minimum number of swaps required.
Example 1:
Input: nums = [2,1,4,3]
Output: 2
Explanation: We can make the permutation semi-ordered using these sequence of operations:
1 - swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
2 - swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than two operations that make nums a semi-ordered permutation.
Example 2:
Input: nums = [2,4,1,3]
Output: 3
Explanation: We can make the permutation semi-ordered using these sequence of operations:
1 - swap i = 1 and j = 2. The permutation becomes [2,1,4,3].
2 - swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
3 - swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than three operations that make nums a semi-ordered permutation.
Example 3:
Input: nums = [1,3,4,2,5]
Output: 0
Explanation: The permutation is already a semi-ordered permutation.
Code
1
2
3