Easy

题目描述

给你一个长度为 n 的下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回使 nums 成为递增数组所需要的 最少右移次数 ，如果无法实现，则返回 -1 。

一次 右移 是指将元素从下标 i 移动到下标 (i + 1) % n ，对所有下标都适用。

示例 1：

输入：nums = [3,4,5,1,2]
输出：2
解释：
第一次右移后，nums = [2,3,4,5,1] 。
第二次右移后，nums = [1,2,3,4,5] 。
现在 nums 已经排好序了，所以答案是 2 。

示例 2：

输入：nums = [1,3,5]
输出：0
解释：nums 已经排好序了，所以答案是 0 。

示例 3：

输入：nums = [2,1,4]
输出：-1
解释：无法通过右移操作使数组排序。

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • nums 包含互不相同的整数。

解题思路

这道题的核心思路是判断数组是否为旋转排序数组，如果是，计算需要多少次右移。

分析过程：

  1. 寻找断点：在一个能通过右移排序的数组中，最多只能有一个位置 i 满足 nums[i] > nums[i+1]（断点）
  2. 验证排序性：断点左右两部分都必须是递增的
  3. 验证连接性：如果存在断点，还需要验证 nums[n-1] <= nums[0]，确保整个数组在旋转后能形成递增序列

具体步骤：

  • 遍历数组找到所有满足 nums[i] > nums[i+1] 的位置
  • 如果断点超过 1 个，返回 -1
  • 如果没有断点，数组已排序，返回 0
  • 如果有 1 个断点在位置 k，检查两个条件：
    • nums[n-1] <= nums[0]（旋转后能连接）
    • 断点前后都是递增的
  • 满足条件则返回 n - k - 1（右移次数）

推荐解法：一次遍历找断点 + 条件验证，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int minimumRightShifts(vector<int>& nums) {
        int n = nums.size();
        int breakPoint = -1;
        
        // 寻找断点
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (breakPoint != -1) {
                    return -1; // 多于一个断点
                }
                breakPoint = i;
            }
        }
        
        // 没有断点，数组已排序
        if (breakPoint == -1) {
            return 0;
        }
        
        // 检查旋转后能否形成递增序列
        if (nums[n - 1] > nums[0]) {
            return -1;
        }
        
        return n - breakPoint - 1;
    }
};

class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        break_point = -1
        
        # 寻找断点
        for i in range(n - 1):
            if nums[i] > nums[i + 1]:
                if break_point != -1:
                    return -1  # 多于一个断点
                break_point = i
        
        # 没有断点，数组已排序
        if break_point == -1:
            return 0
        
        # 检查旋转后能否形成递增序列
        if nums[n - 1] > nums[0]:
            return -1
        
        return n - break_point - 1

public class Solution {
    public int MinimumRightShifts(IList<int> nums) {
        int n = nums.Count;
        int breakPoint = -1;
        
        // 寻找断点
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (breakPoint != -1) {
                    return -1; // 多于一个断点
                }
                breakPoint = i;
            }
        }
        
        // 没有断点，数组已排序
        if (breakPoint == -1) {
            return 0;
        }
        
        // 检查旋转后能否形成递增序列
        if (nums[n - 1] > nums[0]) {
            return -1;
        }
        
        return n - breakPoint - 1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumRightShifts = function(nums) {
    const n = nums.length;
    let breakPoint = -1;
    
    for (let i = 0; i < n - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            if (breakPoint !== -1) return -1;
            breakPoint = i;
        }
    }
    
    if (breakPoint === -1) return 0;
    
    if (nums[n - 1] > nums[0]) return -1;
    
    return n - breakPoint - 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要一次遍历数组找断点
空间复杂度O(1)只使用常数额外空间