检查数组是否被分类并旋转

文章小白一枚，正在不断学习积累知识，现将学习到的知识记录一下，也是将我的所得分享给大家！而今天这篇文章《检查数组是否被分类并旋转》带大家来了解一下##content_title##，希望对大家的知识积累有所帮助，从而弥补自己的不足，助力实战开发！

题目：1752. 检查数组是否已排序并旋转

难度：中等

主题：数组

给定一个数组 nums，如果该数组最初按非递减顺序排序，然后旋转了任意数量的位置（包括零），则返回 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

提示：

1. 暴力法，检查是否可以从每个位置开始构造排序数组。

解决方案：

我们需要确定是否可以通过旋转一个按非递减顺序排序的数组来得到给定的数组。以下是实现此目标的分步方法：

1. 检查数组是否已排序：如果数组已排序，则意味着它可以旋转 0 个位置得到自身，因此我们应该返回 true。

2. 找到枢轴点：枢轴点是顺序中断的位置，即 nums[i] > nums[i + 1]。该枢轴点表示旋转点。

3. 检查顺序：找到枢轴点后，我们需要确保数组在枢轴点之前和之后都是按非递减顺序排序的。

4. 处理重复项：如果存在重复项，我们需要确保枢轴点是唯一顺序中断点。

让我们在 PHP 中实现此解决方案：

<?php
function check($nums) {
    $n = count($nums);
    $breaks = 0;
    for ($i = 0; $i < $n; $i++) {
        if ($nums[$i] > $nums[($i + 1) % $n]) {
            $breaks++;
        }
    }
    return $breaks <= 1;
}

// 测试用例
$nums1 = [3,4,5,1,2];
$nums2 = [2,1,3,4];
$nums3 = [1,2,3];
$nums4 = [1,1,1]; //测试重复项
$nums5 = [2,1,1,1]; //测试重复项

var_dump(check($nums1)); // 输出：bool(true)
var_dump(check($nums2)); // 输出：bool(false)
var_dump(check($nums3)); // 输出：bool(true)
var_dump(check($nums4)); // 输出：bool(true)
var_dump(check($nums5)); // 输出：bool(true)
?>

解释：

1. 识别排序中断：扫描数组，我们计算当前元素大于下一个元素的次数（考虑使用模运算符进行旋转）。“中断”是违反排序顺序的地方。

2. 验证旋转：对于排序并旋转的数组，在排序顺序中最多应该只有一个中断。

3. 返回结果：如果中断次数超过 1，则该数组不能被视为排序并旋转的数组。

4. 复杂度：

   • 时间复杂度：O(n) - 只有一个循环遍历数组。
   • 空间复杂度：O(1) - 没有使用额外的存储空间。

此方法确保我们能够正确识别是否可以通过旋转一个排序数组来得到给定的数组。

联系方式：如果您觉得本系列文章有帮助，请考虑在 GitHub 上为我的代码库点赞，或在您喜欢的社交网络上分享此文章。您的支持对我意义重大！如果您想了解更多类似的有用内容，请随时关注我：

• LinkedIn
• GitHub

理论要掌握，实操不能落！以上关于《检查数组是否被分类并旋转》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！