Easy

题目描述

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

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

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

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

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

示例 1：

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

示例 2：

输入：nums = [2,4,1,3]
输出：3
解释：我们可以通过下述操作序列将排列变为半有序排列：
1 - 交换下标 i = 1 和 j = 2 对应的元素。排列变为 [2,1,4,3] 。
2 - 交换下标 i = 0 和 j = 1 对应的元素。排列变为 [1,2,4,3] 。
3 - 交换下标 i = 2 和 j = 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 是一个排列

解题思路

解题思路

这道题的核心是理解我们需要通过相邻元素交换，将数字 1 移动到第一个位置，将数字 n 移动到最后一个位置。

分析过程：

  1. 找到关键位置：首先找到数字 1 和数字 n 在数组中的位置，设为 pos1 和 posN
  2. 计算移动步数：
    • 将 1 移动到位置 0 需要 pos1 步（每次向左交换一位）
    • 将 n 移动到位置 n-1 需要 (n-1-posN) 步（每次向右交换一位）
  3. 处理重叠情况：如果 pos1 > posN，说明在移动过程中，1 和 n 会相遇并交换位置，这样可以节省 1 次操作

具体计算公式：

  • 如果 pos1 < posN：答案 = pos1 + (n-1-posN)
  • 如果 pos1 > posN：答案 = pos1 + (n-1-posN) - 1

这是因为当 1 在 n 的右边时，在移动过程中它们会相遇，相当于同时完成了一次交换，节省了一步操作。

代码实现

class Solution {
public:
    int semiOrderedPermutation(vector<int>& nums) {
        int n = nums.size();
        int pos1 = 0, posN = 0;
        
        // 找到1和n的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                pos1 = i;
            }
            if (nums[i] == n) {
                posN = i;
            }
        }
        
        // 计算最小操作次数
        int operations = pos1 + (n - 1 - posN);
        
        // 如果1在n的右边，移动过程中会相遇，节省一次操作
        if (pos1 > posN) {
            operations--;
        }
        
        return operations;
    }
};

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        n = len(nums)
        pos1 = nums.index(1)
        posN = nums.index(n)
        
        # 计算最小操作次数
        operations = pos1 + (n - 1 - posN)
        
        # 如果1在n的右边，移动过程中会相遇，节省一次操作
        if pos1 > posN:
            operations -= 1
            
        return operations

public class Solution {
    public int SemiOrderedPermutation(int[] nums) {
        int n = nums.Length;
        int pos1 = 0, posN = 0;
        
        // 找到1和n的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                pos1 = i;
            }
            if (nums[i] == n) {
                posN = i;
            }
        }
        
        // 计算最小操作次数
        int operations = pos1 + (n - 1 - posN);
        
        // 如果1在n的右边，移动过程中会相遇，节省一次操作
        if (pos1 > posN) {
            operations--;
        }
        
        return operations;
    }
}

var semiOrderedPermutation = function(nums) {
    const n = nums.length;
    let pos1 = 0, posN = 0;
    
    // 找到1和n的位置
    for (let i = 0; i < n; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次找到元素1和n的位置
空间复杂度O(1)只使用了常数个额外变量