[2717]半有序排列⭐
题目描述
给你一个下标从 0 开始、长度为 n 的整数排列 nums 。
如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：
选择 nums 中相邻的两个元素，然后交换它们。
返回使 nums 变成 半有序排列 所需的最小操作次数。
排列 是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。
示例输入
示例 1：
输入：nums = [2, 1, 4, 3]
输出：2
- 交换下标 0 和下标 1 对应元素。排列变为 [1, 2, 4, 3]
- 交换下标 2 和下标 3 对应元素。排列变为 [1, 2, 3, 4]
示例 2：
输入：nums = [4, 2, 1, 3]
输出：4
- 交换下标 0 和下标 1 对应元素。排列变为 [2, 4, 1, 3]
- 交换下标 1 和下标 2 对应元素。排列变为 [2, 1, 4, 3]
- 交换下标 0 和下标 1 对应元素。排列变为 [1, 2, 4, 3]
- 交换下标 2 和下标 3 对应元素。排列变为 [1, 2, 3, 4]
示例 3：
输入：nums = [1, 2, 3, 4, 5]
输出：0
不需要任何操作就是半有序序列。
题解
这个题思路还是比较清晰的。
我们要找到 1 在数组中的位置index1和 n 在数组中的位置index2。
如果 1 在 n 的前面，那么很简单，我们要把 1 挪到最前面，把 n 挪到最后面。
而如果 n 在 1 的前面，我们在把 1 挪到最前面，把 n 挪到最后面这个过程中多交换了一次。因为数字 1 在移动到起始位置时，可能会与数字 n 交错。
public int semiOrderedPermutation(int[] nums) {int n = nums.length;int ans;int index1 = 0, index2 = 0;for (int i = 0; i < n; i++) {if (nums[i] == 1) {index1 = i;}if (nums[i] == n) {index2 = i;}}if (index1 < index2) {ans = index1 + n - 1 - index2;} else {ans = index1 + n - 1 - index2 - 1;}return ans;
}