Leetcode每日一题 —— 3942. 排序排列的最少操作数

开发调优
,
1

思路

观察可发现，反转和左旋并不能改变数组的顺序。所以如果数组本身是无序的，那肯定是无法操作到递增的。
然后就是需要几次的问题，只要找到0与n-1的连接处，就可以计算需要操作的次数了。
如果本身是正序，那就有反转->左旋n次->反转 或者 不反转->左旋n次两种方式。
如果本身是倒序，那就有反转->左旋n次 或者 左旋n次->反转两种方式。

PS

佬友们几天不见，这几天经常是写一半就忙起来了，甚至都没时间写，回头看看也不知道在忙啥。不过有的忙终归是好事吧，大概 :joy:

代码

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);
    }
}
5 个赞
2

把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;
	}
};
1 个赞
3

忙，忙点好啊.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;
    }
};
4

通过相邻元素差值判断数组的方向，再利用断点 pos 计算操作次数。

无序排列返回 -1

对升序排列，有两种选择

  1. 直接左旋
  2. 翻转一次，把左旋方向转换成右旋方向，再翻转回来（两次翻转可以模拟向右旋转，而且成本只增加 2）

对降序排列

  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);
    }
};
5

顺便一提，这道题还可以牵涉到循环群与二面体群的关系

6

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
        }
    }
}