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

Constanline · October 22, 2026, 1:32am

思路

观察可发现，反转和左旋并不能改变数组的顺序。所以如果数组本身是无序的，那肯定是无法操作到递增的。
然后就是需要几次的问题，只要找到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);
    }
}

tiansuohaoer · October 22, 2026, 1:49am

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

SomeBottle · October 22, 2026, 2:42am

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

darker233 · October 22, 2026, 2:50am

通过相邻元素差值判断数组的方向，再利用断点 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);
    }
};

darker233 · October 22, 2026, 2:55am

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

o8080x · October 22, 2026, 3:21am

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

Fengfeng10 · October 22, 2026, 11:14am

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut has_drop: bool = false;
        let mut is_asc: bool = true;
        let mut is_desc: bool = true;
        let mut zero_index: usize = 0;
        let n = nums.len();
        if (nums[0] - nums[n - 1]).abs() > 1 && (nums[0] - nums[n - 1]).abs() != n as i32 - 1{
            has_drop = true;
        }
        for i in 0..n {
            if nums[i] == 0 {
                zero_index = i;
            }
            if i + 1 == n {
                continue;
            }
            let should_skip_flip: bool = (nums[i] - nums[i + 1]).abs() == n as i32 - 1;
            if nums[i] > nums[i + 1] && !should_skip_flip {
                is_asc = false;
            }
            if nums[i] < nums[i + 1] && !should_skip_flip {
                is_desc = false;
            }
            if (nums[i] - nums[i + 1]).abs() > 1 && (nums[i] - nums[i + 1]).abs() != n as i32 - 1{
                if has_drop == true {
                    return -1;
                }
                has_drop = true;
            }
        }
        if (!is_asc) && (!is_desc) {
            return -1;
        }
        if is_asc {
            return (zero_index).min(2 + n - zero_index) as i32;
        }
        if is_desc {
            return (n - zero_index).min(zero_index + 2) as i32;
        }
        0
    }
}

www

Fengfeng10 · October 22, 2026, 11:15am

听起来好复杂的样子w

CPython · October 22, 2026, 12:35pm

不会写,分析了一波没有时间了, 来一个这个吧 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if root is q or root is p:
            return root
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if l and r:
            return root
        return l or r

Qiansui · October 22, 2026, 1:44pm

分类讨论啦，WA 了两发才想明白 qwq

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int id = 0, n = nums.size(), ans = -1;
        for(int i = 0; i < n; ++ i){
            if(nums[i] == 0){
                id = i;
            }
            int d = abs(nums[i] - nums[(i + 1) % n]);
            if(d != 1 && d != n - 1) return ans;
        }
        ans = 0;
        if(n > 1){
            int dir = nums[(id + 1) % n] == nums[id] + 1;
            if(dir) ans = min(id, n - id + 2);
            else ans = min(id + 2, n - id);
        }
        return ans;
    }
};

Topic		Replies	Views
Leetcode每日一题 —— 1658. 将 x 减到 0 的最小操作数开发调优 Leetcode , 算法	7	124	September 24, 2026
Leetcode每日一题 —— 153. 寻找旋转排序数组中的最小值开发调优 Leetcode , 算法	3	88	May 15, 2026
Leetcode每日一题 —— 3551. 数位和排序需要的最小交换次数开发调优 Leetcode , 算法	8	116	October 17, 2026
Leetcode每日一题 —— 154. 寻找旋转排序数组中的最小值 II 开发调优 Leetcode , 算法	7	111	May 17, 2026
Leetcode每日一题 —— 3634. 使数组平衡的最少移除数目开发调优 Leetcode , 算法	10	212	February 10, 2026

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

思路

PS

代码

Related topics