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

🟢   🔖  数组  🔗 力扣 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 之前	[✓]	字符串	🟢	🀄️ 🔗