What is the minimum number of operations to make nums a semi-ordered permutation?

The minimum number of operations is determined by finding the positions of 1 and n and calculating how many swaps are necessary to place 1 at the start and n at the end.

How do I handle the edge case where the permutation is already semi-ordered?

If the permutation is already semi-ordered, no swaps are needed, and the answer should be 0.

What if 1 and n are close to each other in the array?

If 1 and n are close to each other, the number of swaps required may be reduced. You should handle these cases by carefully calculating the moves needed for both numbers without unnecessary swaps.

What is the time complexity of solving this problem?

The time complexity is O(n), as you need to find the positions of 1 and n, which involves a single scan of the array.

Can this problem be solved in less than O(n) time?

No, this problem requires at least one scan through the array to find the positions of 1 and n, so O(n) is the best time complexity.

#2717

Easy

auto_awesome数组·模拟

LeetCode 题解工作台

半有序排列

给你一个下标从 0 开始、长度为 n 的整数排列 nums 。如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为半有序排列。你可以执行多次下述操作，直到将 nums 变成一个半有序排列：选择 nums 中相邻的两个元素，然后交换它们。返回使 nums 变成半有序排列所…

数组模拟

题目描述

给你一个下标从 0 开始、长度为 n 的整数排列 nums 。

如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：

选择 nums 中相邻的两个元素，然后交换它们。

返回使 nums 变成 半有序排列 所需的最小操作次数。

排列是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。

示例 1：

输入：nums = [2,1,4,3]
输出：2
解释：可以依次执行下述操作得到半有序排列：
1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明，要让 nums 成为半有序排列，不存在执行操作少于 2 次的方案。

示例 2：

输入：nums = [2,4,1,3]
输出：3
解释：
可以依次执行下述操作得到半有序排列：
1 - 交换下标 1 和下标 2 对应元素。排列变为 [2,1,4,3] 。
2 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
3 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明，要让 nums 成为半有序排列，不存在执行操作少于 3 次的方案。

示例 3：

输入：nums = [1,3,4,2,5]
输出：0
解释：这个排列已经是一个半有序排列，无需执行任何操作。

提示：

2 <= nums.length == n <= 50
1 <= nums[i] <= 50
nums 是一个排列

lightbulb

解题思路

方法一：寻找 1 和 n 的位置

我们可以先找到 $1$ 和 $n$ 的下标 $i$ 和 $j$ ，然后根据 $i$ 和 $j$ 的相对位置，判断需要交换的次数。

如果 $i \lt j$ ，那么需要交换的次数为 $i + n - j - 1$ ；如果 $i \gt j$ ，那么需要交换的次数为 $i + n - j - 2$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        n = len(nums)
        i = nums.index(1)
        j = nums.index(n)
        k = 1 if i < j else 2
        return i + n - j - k

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for how well the candidate identifies the positions of 1 and n.
question_mark
Evaluate if the candidate optimizes the number of swaps needed for edge cases.
question_mark
Check how the candidate handles scenarios where the permutation is already semi-ordered.

warning

常见陷阱

外企场景

error
Candidates may not properly consider edge cases where the array is already semi-ordered.
error
There might be confusion with how to calculate the number of swaps when 1 and n are close to each other.
error
Not optimizing the number of operations in cases where no swaps are necessary.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the permutation is larger than 50 elements?
arrow_right_alt
How would the problem change if the first and last elements were arbitrary numbers instead of 1 and n?
arrow_right_alt
What if you were allowed to move elements around in groups rather than just swapping?

help

常见问题

外企场景

继续练习

#2744 最大字符串配对数目 #2751 机器人碰撞 #2682 找出转圈游戏输家