半有序排列

难度: Easy

给你一个下标从 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 是一个排列

Submission

运行时间: 27 ms

内存: 16.0 MB

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        firstIdx = nums.index(1)
        lastIdx = nums.index(len(nums))

        omni = 0 if firstIdx < lastIdx else 1

        return firstIdx + len(nums) - 1 - lastIdx - omni

Explain

该题解的核心思路是通过计算将数字1和数字n移动到序列的首尾所需的最小交换次数。首先，找到数字1 (firstIdx) 和数字n (lastIdx) 在序列中的位置。如果数字1在数字n之前（firstIdx < lastIdx），则我们只需要分别将这两个数字移动到序列的两端。如果数字n在数字1之前（firstIdx > lastIdx），则在移动的同时需要多执行一次交换（omni为1），这是因为当1在n的右边时，将它们移到两端后，它们的相对位置仍然需要调整。最终的最小操作次数计算为firstIdx加上从lastIdx到序列末尾的距离，再减去omni。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        # 找到数字1和数字n在数组中的索引
        firstIdx = nums.index(1)
        lastIdx = nums.index(len(nums))

        # 如果1在n的右边，则多一次操作调整它们的相对位置
        omni = 0 if firstIdx < lastIdx else 1

        # 计算将1移到开始位置，n移到结束位置所需的操作总数，考虑是否需要额外调整
        return firstIdx + len(nums) - 1 - lastIdx - omni

Explore

使用索引位置来计算交换次数而不直接操作数组的原因是效率和简化问题的复杂性。直接操作数组进行交换会涉及到实际的数组元素移动，这可能导致算法的时间复杂度增加，并且在实现上更为复杂。而通过计算索引位置的偏移，我们可以直接得到需要的交换次数，这样做既可以减少计算量，也使得算法更加清晰易懂。此外，这种方法也便于理论分析和算法的证明。

在算法中，`omni`变量用于处理特殊情况，即当数字1在数字n的右侧时（即`firstIdx > lastIdx`），这意味着数字1和数字n在最终的半有序排列中不仅要移动到数组的两端，还需要调整它们的相对位置。例如，对于数组`[2, 3, 1, 4]`，数字1的索引是2，数字4（n）的索引是3。在将1移动到数组的开始，将4移动到数组的末尾后，我们发现在排序过程中，1和4的相对位置需要额外的一次交换才能正确地放置。因此，`omni`被设置为1，以表示这种额外的交换需求。

当数字1和数字n的索引相同时，这意味着1和n是同一个数字，即数组长度为1，且只包含一个元素`1`。在这种特殊情况下，数组实际上已经是一个半有序排列，因为它的首尾元素分别是1和n。因此，不需要任何交换操作，操作次数为0。这种情况在算法中是隐含处理的，因为如果数组仅有一个元素，那么`firstIdx`和`lastIdx`都为0，且`omni`不会增加任何额外的交换次数，结果自然为0。