2717. Semi-Ordered Permutation
Description
You are given a 0-indexed permutation of n
integers nums
.
A permutation is called semi-ordered if the first number equals 1
and the last number equals n
. You can perform the below operation as many times as you want until you make nums
a semi-ordered permutation:
- Pick two adjacent elements in
nums
, then swap them.
Return the minimum number of operations to make nums
a semi-ordered permutation.
A permutation is a sequence of integers from 1
to n
of length n
containing each number exactly once.
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.
Constraints:
2 <= nums.length == n <= 50
1 <= nums[i] <= 50
nums is a permutation.
Solutions
Solution 1: Find the Positions of 1 and n
We can first find the indices $i$ and $j$ of $1$ and $n$, respectively. Then, based on the relative positions of $i$ and $j$, we can determine the number of swaps required.
If $i < j$, the number of swaps required is $i + n - j - 1$. If $i > j$, the number of swaps required is $i + n - j - 2$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|