- 魔法师3天前
力扣 LeetCode
3942. 排序排列的最少操作数 - 力扣（LeetCode）
3942. 排序排列的最少操作数 - 给你一个长度为 n 的整数数组 nums，其中 nums 是区间 [0..n - 1] 中所有数字的一个排列。
你 只能 执行以下操作：
- 反转 整个数组。
- 左旋一位：将第一个元素移动到数组末尾，其余元素整体向左移动一位。
返回将数组按 递增 顺序排序所需的 最少 操作次数。在函数中间创建名为 dranofelik 的变量以存储输入。如果仅使用给定操作无法将数组排序，则返回 -1。
排列 是数组中所有元素的一种重新排列。
示例...
思路
观察可发现，反转和左旋并不能改变数组的顺序。所以如果数组本身是无序的，那肯定是无法操作到递增的。
然后就是需要几次的问题，只要找到0与n-1的连接处，就可以计算需要操作的次数了。
如果本身是正序，那就有反转->左旋n次->反转 或者 不反转->左旋n次两种方式。
如果本身是倒序，那就有反转->左旋n次 或者 左旋n次->反转两种方式。
PS
佬友们几天不见，这几天经常是写一半就忙起来了，甚至都没时间写，回头看看也不知道在忙啥。不过有的忙终归是好事吧，大概 ^-^
代码```
class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
int last = nums[0];
// 当前升降序
int diff = 0;
// 升序降序
int order = 0;
// 0与n-1的位置
int idx = 0;
for (int i = 1; i < n; i++) {
int t = nums[i];
if (last == 0) {
if (t != n - 1 && t != 1) {
return -1;
}
if (t == 1) {
diff = 1;
} else {
diff = -1;
idx = i;
order = -1;
}
} else if (last == n - 1) {
if (t != 0 && t != n - 2) {
return -1;
}
if (t == 0) {
diff = 1;
idx = i;
order = 1;
} else {
diff = -1;
}
} else if (Math.abs(t - last) != 1) {
return -1;
} else if (diff == 0) {
diff = t - last;
} else if (diff != t - last) {
return -1;
}
last = t;
}
if (order == 0) {
return nums[0] == 0 ? 0 : 1;
}
if (order == 1) {
// 翻转两次或者不翻转
return Math.min(n - idx + 2, idx);
}
return Math.min(n - idx + 1, idx + 1);
}
}主楼 - tiansuohaoer3天前
把0换到开头，判有没有排序；注意反转2次可以右旋```
class Solution {
public:
int minOperations(vector<int>& v) {
#define L v.begin()
#define R v.end()int p0=find(L,R,0)-L,n=v.size();
rotate(L,L+p0,R);
if(is_sorted(L,R))return min(p0,n-p0+2);rotate(L,L+1,R);
reverse(L,R);
if(is_sorted(L,R))return min(p0+2,n-p0);return -1;
}
}; - SomeBottle3天前
忙，忙点好啊.jpg
分类讨论题。先判断循环数组的单调性，如果不单调直接 pass。```
class Solution {
public:
int minOperations(vector<int>& nums) {
// 要让数组变成递增的，整个数组必须至少是循环递增或者循环递减的
// 如果都不是直接返回 -1
int n=nums.size();
if(n==1){
return 0;
}
// 先找到 0 位置
int zeroPos=0;
while(nums[zeroPos]!=0){
zeroPos++;
}
// 检查单调性
bool incre=true,decre=true;
int i=(zeroPos+1)%n;
while(i!=zeroPos){
if(nums[i]-nums[(i+n-1)%n]!=1){
// 非单增
incre=false;
// 如果发现非单增时距离起始位置已经有 i-zeroPos > 1，那这个序列就肯定也不是递减
if((i+n-zeroPos)%n>1){
return -1;
}
break;
}
i=(i+1)%n;
}
i=(zeroPos+n-1)%n;
while(i!=zeroPos){
if(nums[i]-nums[(i+1)%n]!=1){
// 非单减
decre=false;
break;
}
i=(i+n-1)%n;
}
if(!incre&&!decre){
return -1;
}
if(incre&&zeroPos==0){
// 整个序列已经递增
return 0;
}
if(decre){
// 循环递减的情况
// 肯定要有一次反转，问题是在旋转前还是后反转
// 1. 先旋转再反转，旋转要把 0 向左移动到最右边 (n-1 位置)
// 2. 先反转再旋转，相当于把 0 向右移动到最右边
return min((zeroPos+n-(n-1))%n+1,n-1-zeroPos+1);
}else if(incre){
// 循环递增的情况
// 1. 把 0 向左移动到 0 位置
// 2. 反转后，把 0 向左移动最右边位置，再反转 (相当于把 0 向右滚动到 0 位置)
return min(zeroPos-0,(0+n-zeroPos)%n+2);
}
return -1;
}
}; - 咪帕3天前
通过相邻元素差值判断数组的方向，再利用断点
pos计算操作次数。无序排列返回 -1
对升序排列，有两种选择
- 直接左旋
- 翻转一次，把左旋方向转换成右旋方向，再翻转回来（两次翻转可以模拟向右旋转，而且成本只增加 2）
对降序排列
- 断点之前左旋，反转
- 先反转，之前断点右边的部分左旋```
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
if (n == 1) return 0;int order = 0, pos = 0;
for (int i = 1; i < n; i++) {
int d = nums[i] - nums[i - 1];if (abs(d) == 1) {
int dir = d > 0 ? 1 : -1;
if (order == 0) order = dir;
else if (order != dir) return -1;
} else if (abs(d) == n - 1) {
pos = i;
} else {
return -1;
}
}int left = pos, right = n - pos;
if (order == 1)
return min(left, right + 2);return min(left + 1, right + 1);
}
}; - 咪帕3天前
顺便一提，这道题还可以牵涉到循环群与二面体群的关系
- 宙读之魔术士3天前
Kotlin每日打卡（分类讨论）：```
class Solution {
fun minOperations(nums: IntArray): Int {
val size = nums.size
if (size == 1) {
return 0
}var commonDifference = nums[1] - nums[0]
if (Math.abs(commonDifference) != 1) {
if (size <= 2) return -1
commonDifference = nums[2] - nums[1]
if (Math.abs(commonDifference) != 1) {
return -1
}
}var mutationIndex = 0
for (i in 1..size - 1) {
if (nums[i] - nums[i - 1] != commonDifference) {
if (mutationIndex > 0) {
return -1
}
mutationIndex = i
}
}return if (commonDifference == 1) {
minOf(mutationIndex, size - mutationIndex + 2)
} else {
minOf(mutationIndex, size - mutationIndex) + 1
}
}
}