2717. Semi-Ordered Permutation

Problem

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.

https://leetcode.cn/problems/semi-ordered-permutation/

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.

Test Cases

1
2

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([2,1,4,3], 2),
    ([2,4,1,3], 3),
    ([1,3,4,2,5], 0),
])
class Test:
    def test_solution(self, nums, expected):
        sol = Solution()
        assert sol.semiOrderedPermutation(nums) == expected

Thoughts

设 1 在 nums 中的位置下标为 a（0-indexed），把它挪到第一位需要交换 a 次。

设 n 在 nums 中的位置下标为 b，把它挪到最后一位需要交换 n - 1 - b 次。

二者相加即为总的交换次数。但是如果开始的时候 n 在 1 左边，它俩交换的时候，一次交换但它俩都挪了位置，所以这种情况下总的交换次数要减去一。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def semiOrderedPermutation(self, nums: list[int]) -> int:
        n = len(nums)
        a = b = -1
        for i, v in enumerate(nums):
            if v == 1:
                a = i
                if b >= 0:
                    a -= 1
                    break
            elif v == n:
                b = n - 1 - i
                if a >= 0:
                    break

        return a + b

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章