[LeetCode] 每日一题 2717. 半有序排列

题目链接

题目描述

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

题解

解题思路

1. 确定关键位置：

   • 找到数字 1 的位置 i1。

   • 找到数字 n 的位置 in。

2. 计算操作次数：

   • 若 i1 在 in 的左侧或重合，则需要：

     • 将 1 移动到最左侧，共需 i1 次操作。

     • 将 n 移动到最右侧，共需 n−1−inn - 1 - inn−1−in 次操作。

     • 总操作次数为：i1+n−1−ini1 + n - 1 - ini1+n−1−in。

   • 若 i1 在 in 的右侧，则需要：

     • 先将 1 移动到最左侧，共需 i1 次操作。

     • 再将 n 移动到最右侧，此时因为 1 和 n 之间原本有一个位置已被占用，需减少 1 次操作：

       • 总操作次数为：i1+n−2−ini1 + n - 2 - ini1+n−2−in。

代码实现

class Solution {
    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        int i1 = -1, in = -1;
        
        // 找到 1 和 n 的位置
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                i1 = i;
            } else if (nums[i] == n) {
                in = i;
            }
            // 如果已找到 1 和 n，可以提前退出循环
            if (i1 != -1 && in != -1) {
                break;
            }
        }
        
        // 根据位置关系计算最小操作次数
        if (i1 <= in) {
            return i1 + n - 1 - in;
        } else {
            return i1 + n - 2 - in;
        }
    }
}

复杂度分析

• 时间复杂度：

  • 查找 1 和 n 的位置需要 O(n) 时间。

  • 因为没有嵌套循环，总复杂度为 O(n)。

• 空间复杂度：

  • 只使用了常量空间，空间复杂度为 O(1)。

总结

本题的核心是通过数学和位置关系快速计算所需操作次数。通过遍历数组确定关键位置，再根据位置关系判断结果，避免了冗余的模拟操作，从而大幅提高了效率。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。