给你一个下标从 0 开始、长度为 n 的整数排列 nums 。 如果排列的第一个数字等于 1 且最后一个数字等于 n ,则称其为 半有序排列 。你可以执行多次下述操作,直到将 nums 变成一个 半有序排列 : 选择 nums 中相邻的两个元素,然后交换它们。 返回使 nums 变成 半有序排列 所需的最小操作次数。 排列 是一个长度为 n 的整数序列,其中包含从 1 到 n 的每个数字恰好一次。 用简单的算法写出Java并带注释
时间: 2024-03-04 20:48:53 浏览: 33
```java
class Solution {
public int minSwaps(int[] nums) {
int n = nums.length;
int left = 0, right = n - 1;
// 找到第一个数字不为 1 的位置
while (left < n && nums[left] == 1) {
left++;
}
// 找到最后一个数字不为 n 的位置
while (right >= 0 && nums[right] == n) {
right--;
}
// 如果已经是半有序排列,直接返回 0
if (left >= right) {
return 0;
}
int res = 0;
// 从 left 开始遍历到 right,每次找到一个当前位置不对的数字,并将其交换到正确的位置上
// 由于数字从 1 到 n 一共只有 n 个,因此交换 n 次后,排列就会变成半有序排列
for (int i = left; i <= right; i++) {
if (nums[i] != i - left + 2) {
int j = i + 1;
while (j <= right && nums[j] != i - left + 2) {
j++;
}
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
res++;
}
}
return res;
}
}
```
注释:该算法通过找到排列中第一个数字不为 1 的位置和最后一个数字不为 n 的位置,然后从左到右遍历排列,每次找到一个当前位置不对的数字,并将其交换到正确的位置上,直到排列变成半有序排列为止。时间复杂度为 O(n^2),因为最坏情况下需要遍历 n 次,并且每次找到正确的位置需要遍历剩余部分,最终得到变为半有序排列所需的最小操作次数。