1752.md

title	description	keywords
1752. 检查数组是否经排序和轮转得到	LeetCode 1752. 检查数组是否经排序和轮转得到题解，Check if Array Is Sorted and Rotated，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1752. 检查数组是否经排序和轮转得到 检查数组是否经排序和轮转得到 Check if Array Is Sorted and Rotated 解题思路 数组

1752. 检查数组是否经排序和轮转得到

🟢 Easy  🔖  数组  🔗 力扣 LeetCode

题目

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

Example 1:

Input: nums = [3,4,5,1,2]

Output: true

Explanation: [1,2,3,4,5] is the original sorted array.

You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].

Example 2:

Input: nums = [2,1,3,4]

Output: false

Explanation: There is no sorted array once rotated that can make nums.

Example 3:

Input: nums = [1,2,3]

Output: true

Explanation: [1,2,3] is the original sorted array.

You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

题目大意

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。

如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true；否则，返回 false 。

源数组中可能存在 重复项 。

注意： 我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。

示例 1：

输入： nums = [3,4,5,1,2]

输出： true

解释：[1,2,3,4,5] 为有序的源数组。

可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。

示例 2：

输入： nums = [2,1,3,4]

输出： false

解释： 源数组无法经轮转得到 nums 。

示例 3：

输入： nums = [1,2,3]

输出： true

解释：[1,2,3] 为有序的源数组。

可以轮转 x = 0 个位置（即不轮转）得到 nums 。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

解题思路

题目要求判断数组是否可以通过旋转成为非递减顺序数组。通过分析，可以总结出关键点：

• 若数组是旋转后形成的非递减序列，则最多只会出现一次由较大元素到较小元素的递减情况。
• 其中，若数组中的数全都相同，则出现 0 次递减情况。

1. 遍历数组并统计递减次数：

   • 遍历数组，检查相邻元素 nums[i-1] 和 nums[i] 是否满足递减条件，即 nums[i-1] > nums[i]。
   • 递减次数记录在变量 count 中。

2. 检查首尾是否递减：

   • 因为数组是循环的，还需要判断最后一个元素和第一个元素之间是否存在递减，即 nums[n-1] > nums[0]。

3. 判断递减次数是否符合要求：

   • 若数组是旋转后形成的非递减序列，则递减次数 count 至多为 1。

复杂度分析

• 时间复杂度：O(n)，遍历数组一次。
• 空间复杂度：O(1)，仅使用常数额外空间。

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */

var check = function (nums) {
	const n = nums.length;
	let count = 0;
	for (let i = 0; i < n; i++) {
		if (nums[i] < nums[i - 1]) count++; // 检查递减次数
	}
	if (nums[n - 1] > nums[0]) count++; // 检查首尾递减
	return count <= 1; // 至多有1次递减
};

相关题目

题号	标题	题解	标签	难度	力扣
2124	检查是否所有 A 都在 B 之前	[✓]	字符串	🟢	🀄️ 🔗