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

题目：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

提示：

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

以上就是检查数组是否被分类并旋转的详细内容，更多请关注php中文网其它相关文章！