LeetCode 1752「Check if Array Is Sorted and Rotated」判定旋转有序数组：暴力、滑动窗口与断点计数的三种解法（NeetCode 题解仓库实战解析）

LeetCode 1752「Check if Array Is Sorted and Rotated」判定旋转有序数组暴力、滑动窗口与断点计数的三种解法NeetCode 题解仓库实战解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 NeetCode 题解仓库中的 check-if-array-is-sorted-and-rotated.md 为核心完整讲解 LeetCode 1752「Check if Array Is Sorted and Rotated」的三种解法暴力旋转匹配、滑动窗口、断点计数及其多语言实现。读完本文你将掌握如何用模运算modulo把数组视为环形结构、如何利用至多一个断点的性质在 O(n) 时间内判定任意数组是否为某个非递减有序数组的旋转结果并规避重复元素与回绕比较这两大高频陷阱。1. 问题本质与前置知识题目要求判断给定数组nums是否由某个非递减non-decreasing有序数组经过若干次旋转得到。旋转定义为把有序数组末尾的若干元素整体搬到开头。例如[1, 2, 3, 4, 5]旋转得到[3, 4, 5, 1, 2]旋转 0 次即原样也是合法输入因此[1, 2, 3]应返回true题目允许重复元素因此[1, 1, 1]、[2, 2, 3, 1, 1]都是合法输入。原文档在开篇列出了三个前置知识点这也是面试中讲解该题的铺垫数组遍历Array Traversal逐个迭代数组并比较相邻元素模运算Modulo Arithmetic用% n处理环形索引的越界回绕wrap-around是旋转数组问题的核心工具有序数组性质Sorted Array Properties理解非递减允许相等与严格递增的区别以及旋转的语义。在原仓库中该题属于数组与哈希类别的典型题型与之配套的还有 rotate-array.md数组旋转操作、find-minimum-in-rotated-sorted-array.md旋转数组找最小值等文章可以互相印证同一套环形 断点分析框架。2. 解法一暴力解法Brute Force2.1 直觉Intuition一个排序后旋转的数组可以看成把某个有序数组从尾部搬若干元素到头部。例如[3, 4, 5, 1, 2]就是[1, 2, 3, 4, 5]旋转后的结果。因此最直接的验证思路是先把输入排序然后检查原数组是否与排序后数组的某个旋转版本完全一致。2.2 算法步骤Algorithm复制输入数组并排序得到有序版本sortedNums枚举所有可能的旋转量i0到n-1对每个i把sortedNums从位置n-i到n-1的元素与nums开头部分比对再把sortedNums从位置0到n-i-1的元素与nums剩余部分比对若某个旋转与nums完全一致返回true全部旋转都不匹配返回false。Python 实现利用pop()与insert(0, ...)逐个右移构建候选序列其余语言则通过双层循环按索引比对class Solution: def check(self, nums: List[int]) - bool: sortedNums sorted(nums) arr [] for i in range(len(nums)): arr.insert(0, sortedNums.pop()) if nums arr sortedNums: return True return Falsepublic class Solution { public boolean check(int[] nums) { int n nums.length; int[] sortedNums nums.clone(); Arrays.sort(sortedNums); for (int i 0; i n; i) { boolean match true; int idx 0; for (int j n - i; j n match; j) { if (nums[idx] ! sortedNums[j]) { match false; } idx 1; } for (int j 0; j n - i match; j) { if (nums[idx] ! sortedNums[j]) { match false; } idx 1; } if (match) return true; } return false; } }class Solution { public: bool check(vectorint nums) { int n nums.size(); vectorint sortedNums nums; sort(sortedNums.begin(), sortedNums.end()); for (int i 0; i n; i) { bool match true; int idx 0; for (int j n - i; j n match; j) { if (nums[idx] ! sortedNums[j]) { match false; } idx; } for (int j 0; j n - i match; j) { if (nums[idx] ! sortedNums[j]) { match false; } idx; } if (match) return true; } return false; } };class Solution { /** * param {number[]} nums * return {boolean} */ check(nums) { const n nums.length; const sortedNums [...nums].sort((a, b) a - b); for (let i 0; i n; i) { let match true; let idx 0; for (let j n - i; j n match; j) { if (nums[idx] ! sortedNums[j]) { match false; } idx; } for (let j 0; j n - i match; j) { if (nums[idx] ! sortedNums[j]) { match false; } idx; } if (match) return true; } return false; } }public class Solution { public bool Check(int[] nums) { int n nums.Length; int[] sortedNums (int[])nums.Clone(); Array.Sort(sortedNums); for (int i 0; i n; i) { bool match true; int idx 0; for (int j n - i; j n match; j) { if (nums[idx] ! sortedNums[j]) { match false; } idx; } for (int j 0; j n - i match; j) { if (nums[idx] ! sortedNums[j]) { match false; } idx; } if (match) return true; } return false; } }func check(nums []int) bool { n : len(nums) sortedNums : make([]int, n) copy(sortedNums, nums) sort.Ints(sortedNums) for i : 0; i n; i { match : true idx : 0 for j : n - i; j n match; j { if nums[idx] ! sortedNums[j] { match false } idx } for j : 0; j n-i match; j { if nums[idx] ! sortedNums[j] { match false } idx } if match { return true } } return false }class Solution { fun check(nums: IntArray): Boolean { val n nums.size val sortedNums nums.clone() sortedNums.sort() for (i in 0 until n) { var match true var idx 0 var j n - i while (j n match) { if (nums[idx] ! sortedNums[j]) { match false } idx j } j 0 while (j n - i match) { if (nums[idx] ! sortedNums[j]) { match false } idx j } if (match) return true } return false } }class Solution { func check(_ nums: [Int]) - Bool { let n nums.count let sortedNums nums.sorted() for i in 0..n { var match true var idx 0 var j n - i while j n match { if nums[idx] ! sortedNums[j] { match false } idx 1 j 1 } j 0 while j n - i match { if nums[idx] ! sortedNums[j] { match false } idx 1 j 1 } if match { return true } } return false } }impl Solution { pub fn check(nums: Veci32) - bool { let n nums.len(); let mut sorted_nums nums.clone(); sorted_nums.sort(); for i in 0..n { let mut matched true; let mut idx 0; let mut j n - i; while j n matched { if nums[idx] ! sorted_nums[j] { matched false; } idx 1; j 1; } j 0; while j n - i matched { if nums[idx] ! sorted_nums[j] { matched false; } idx 1; j 1; } if matched { return true; } } false } }2.3 复杂度分析时间复杂度O(n²)。排序本身为 O(n log n)但外层枚举 n 种旋转、内层每次比较 O(n) 个元素整体以 O(n²) 为主导Python 版本中insert(0, ...)也是 O(n) 操作空间复杂度O(n)。需要一份排序副本以及 Python 版本中临时构建的arr。该解法作为验证定义的基线方案足够直观适合在面试中先给出再逐步优化。3. 解法二滑动窗口Sliding Window3.1 直觉Intuition如果把数组想象成环形最后一个元素与第一个元素相连那么一个合法的排序后旋转数组必然存在一段长度为 n 的连续、非递减的子序列。借助模运算把数组概念上翻倍就可以用滑动窗口在 O(n) 时间内扫描这段连续区域。3.2 算法步骤Algorithm让索引从1遍历到2n-1通过i % n把数组当作环形访问维护一个变量count记录连续非递减相邻对的数量若当前位置元素nums[i % n]大于等于前一个元素nums[(i-1) % n]则count加一否则说明断点出现把count重置为1一旦count达到n说明找到了完整的长度为 n 的非递减环返回true循环结束后兜底处理n 1的边界情况单元素数组天然满足条件返回n 1。class Solution: def check(self, nums: List[int]) - bool: N len(nums) count 1 for i in range(1, 2 * N): if nums[(i - 1) % N] nums[i % N]: count 1 else: count 1 if count N: return True return N 1public class Solution { public boolean check(int[] nums) { int N nums.length; int count 1; for (int i 1; i 2 * N; i) { if (nums[(i - 1) % N] nums[i % N]) { count; } else { count 1; } if (count N) { return true; } } return N 1; } }class Solution { public: bool check(vectorint nums) { int N nums.size(); int count 1; for (int i 1; i 2 * N; i) { if (nums[(i - 1) % N] nums[i % N]) { count; } else { count 1; } if (count N) { return true; } } return N 1; } };class Solution { /** * param {number[]} nums * return {boolean} */ check(nums) { const N nums.length; let count 1; for (let i 1; i 2 * N; i) { if (nums[(i - 1) % N] nums[i % N]) { count; } else { count 1; } if (count N) { return true; } } return N 1; } }public class Solution { public bool Check(int[] nums) { int N nums.Length; int count 1; for (int i 1; i 2 * N; i) { if (nums[(i - 1) % N] nums[i % N]) { count; } else { count 1; } if (count N) { return true; } } return N 1; } }func check(nums []int) bool { N : len(nums) count : 1 for i : 1; i 2*N; i { if nums[(i-1)%N] nums[i%N] { count } else { count 1 } if count N { return true } } return N 1 }class Solution { fun check(nums: IntArray): Boolean { val N nums.size var count 1 for (i in 1 until 2 * N) { if (nums[(i - 1) % N] nums[i % N]) { count } else { count 1 } if (count N) { return true } } return N 1 } }class Solution { func check(_ nums: [Int]) - Bool { let N nums.count var count 1 for i in 1..(2 * N) { if nums[(i - 1) % N] nums[i % N] { count 1 } else { count 1 } if count N { return true } } return N 1 } }impl Solution { pub fn check(nums: Veci32) - bool { let n nums.len(); let mut count 1; for i in 1..2 * n { if nums[(i - 1) % n] nums[i % n] { count 1; } else { count 1; } if count n { return true; } } n 1 } }3.3 复杂度分析时间复杂度O(n)。只做一次线性扫描最多2n-1次比较空间复杂度O(1)。仅用一个计数器无需额外数组。需要特别说明的是比较符号必须为非递减如果误写成那么包含重复元素的合法输入如[1, 1, 1]会被错误判定为非法。这一点与下方常见陷阱中的严格递增问题同源。4. 解法三迭代计数断点Iteration4.1 直觉Intuition在一个排序后旋转的数组中至多只可能出现一个断点——即某个较大元素后面紧跟着一个较小元素这个位置正是旋转发生的地方。如果遍历完整圈后发现断点不止一个那么数组必然不是某个有序数组的旋转结果。这是三种解法中最精炼、最符合 O(1) 空间约束的写法也是 NeetCode 视频中重点讲解的最终形态。4.2 算法步骤Algorithm初始化断点计数器count遍历数组把每个元素与下一个元素比较其中下一个元素用模运算(i 1) % N计算从而把最后一个元素与第一个元素也纳入比较回绕检查若nums[i] nums[(i 1) % N]说明此处是下降断点count加一若count一旦超过1立即返回false剪枝全部比较结束后返回true断点数至多为 1。class Solution: def check(self, nums: List[int]) - bool: count, N 0, len(nums) for i in range(N): if nums[i] nums[(i 1) % N]: count 1 if count 1: return False return Truepublic class Solution { public boolean check(int[] nums) { int count 0, N nums.length; for (int i 0; i N; i) { if (nums[i] nums[(i 1) % N] count 1) { return false; } } return true; } }class Solution { public: bool check(vectorint nums) { int count 0, N nums.size(); for (int i 0; i N; i) { if (nums[i] nums[(i 1) % N] count 1) { return false; } } return true; } };class Solution { /** * param {number[]} nums * return {boolean} */ check(nums) { let count 0, N nums.length; for (let i 0; i N; i) { if (nums[i] nums[(i 1) % N] count 1) { return false; } } return true; } }public class Solution { public bool Check(int[] nums) { int count 0, N nums.Length; for (int i 0; i N; i) { if (nums[i] nums[(i 1) % N] count 1) { return false; } } return true; } }func check(nums []int) bool { count, N : 0, len(nums) for i : 0; i N; i { if nums[i] nums[(i1)%N] { count if count 1 { return false } } } return true }class Solution { fun check(nums: IntArray): Boolean { var count 0 val N nums.size for (i in 0 until N) { if (nums[i] nums[(i 1) % N]) { count if (count 1) { return false } } } return true } }class Solution { func check(_ nums: [Int]) - Bool { var count 0 let N nums.count for i in 0..N { if nums[i] nums[(i 1) % N] { count 1 if count 1 { return false } } } return true } }impl Solution { pub fn check(nums: Veci32) - bool { let n nums.len(); let mut count 0; for i in 0..n { if nums[i] nums[(i 1) % n] { count 1; if count 1 { return false; } } } true } }实现细节Java / C / JavaScript / C# 版本把count与判断合并进条件表达式 count 1利用短路求值实现先自增、超过 1 才返回 false代码更紧凑Python / Go / Kotlin / Swift / Rust 版本则显式写成两条语句可读性更强。两种风格等价面试时按语言习惯选择即可。4.3 复杂度分析时间复杂度O(n)。单次线性扫描空间复杂度O(1)。仅一个计数器。4.4 与解法二的本质联系解法二滑动窗口统计连续非递减的长度本质是从正面确认存在长度为 n 的合法环解法三断点计数则是从反面确认下降位置至多一处。两者共用同一个数学事实——旋转有序数组在环形视角下只有一段下降沿因此殊途同归复杂度也完全相同。5. 三种解法复杂度对比解法核心思路时间复杂度空间复杂度是否适合面试首选暴力Brute Force排序后逐一比对所有旋转O(n²)O(n)作为基线先给出验证思路滑动窗口Sliding Window环形视角下找长度为 n 的非递减段O(n)O(1)可作为中间过渡方案断点计数Iteration下降断点至多一个O(n)O(1)最优解推荐最终提交6. 常见陷阱Common Pitfalls6.1 忘记检查回绕Wrap-Around旋转有序数组是环形的因此必须把最后一个元素与第一个元素做比较。如果直接写nums[i] nums[i 1]当断点恰好出现在数组末尾与开头之间时例如[2, 1]的断点在2与末尾回绕到1之间或者[3, 4, 5, 1, 2]中5与1之间会漏判。# Wrong: if nums[i] nums[i 1] # Correct: if nums[i] nums[(i 1) % N]这正是原文档反复强调的核心点也是本问题与普通检查数组是否有序问题的最大区别所在。6.2 误以为必须严格递增Strictly Increasing题目语义是非递减允许重复。如果错误地使用nums[i] nums[i1]把相等也当作断点之类的严格递增判断会把[1, 1, 1]、[2, 2, 3, 1, 1]这类合法输入错误地判为非法。正确写法是仅在严格大于时才算断点在大于等于时继续累积连续段。7. 仓库中的多语言实现与延伸阅读本仓库是 NeetCode 题解仓库README.md 明确说明其承载 NeetCode.io 站点与视频中的题解文章目录遵循 articles/README.md 规定的规范每种题解需与 NeetCode 视频中的解法保持一致、给出时间与空间复杂度、尽量覆盖全部相关解法。原文档正是按照这一规范为本题提供了 10 种语言的完整实现Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust与仓库按语言分目录的组织方式一一对应。阅读本文时可以结合以下仓库内相关资源加深对旋转数组这一主题的理解rotate-array.md数组旋转操作本身LeetCode 189理解旋转如何改变元素相对位置find-minimum-in-rotated-sorted-array.md在旋转有序数组中定位最小值同样依赖断点分析search-in-rotated-sorted-array-ii.md 及其多语言实现如 python/0081-search-in-rotated-sorted-array-ii.py、python/0033-search-in-rotated-sorted-array.py在允许重复的旋转有序数组中搜索目标值进一步体会重复元素 环形结构的边界处理hints/find-target-in-rotated-sorted-array.md仓库 hints 目录为同类题目提供的解题提示可用于面试前的快速回顾。这些文章与本题共享环形取模 断点定位的方法论建议串起来系统学习把零散技巧沉淀为一套可迁移的数组题解题框架。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考