LeetCode解法：1752.检查数组是否有序旋转

🔄 LeetCode 1752：汝能反旋此数组乎？（初学者指南）

噫吁嚱，同道编程者！👋 吾乃Vansh2710，今欲解此LeetCode之趣题。今日所攻，乃1752题：“验数组是否有序且已旋”。似是谜题，然勿忧，吾等将逐段剖析，揭其至雅之解法！

此题实乃砥砺数组操作与逻辑思辨之良方。初看似繁，然一法简出，则豁然开朗。且共探之！

其题何在？🧐

试想君有一列数，已至完美之序，如 [1, 2, 3, 4, 5].
今复想君 而旋之 之理。此谓取其首部之素，移置末尾，而序仍其旧。

譬如，若将 [1, 2, 3, 4, 5] 旋移二位：

[1, 2, 3, 4, 5]
取 1, 2 而移置末尾： [3, 4, 5, 1, 2]

问题是： 已知数组 nums，吾辈能否知其 是否可由 原本已排序（非递减），继而旋转若干次（或为零次）？

须知要旨：

非递减序： [1, 2, 2, 3]已排序。[3, 2, 1]未排序。
旋转：可任意位数，包括零位（不旋转）。
允许重复。此乃要旨！[3, 4, 5, 5, 1, 2]或可也[1, 2, 3, 4, 5, 5]已旋。

吾等观其例焉。

nums = [3, 4, 5, 1, 2]
- 岂非[1, 2, 3, 4, 5]已排序乎？然。
- 能[1, 2, 3, 4, 5]旋之而得[3, 4, 5, 1, 2]然，转二位。
- 輸出：true
nums = [2, 1, 3, 4]
- 若排序之，则为[1, 2, 3, 4].
- 乎[1, 2, 3, 4] 可转乎为 [2, 1, 3, 4]？不可。2, 1 之部，破单转所维之序也。
- 输出：false
nums = [1, 2, 3]
- 其序已治乎？是。
- 可转以得 [1, 2, 3]？可，零转而已。
- 输出：true

“啊哈！”之悟——吾之直觉 ✨

思一真正已排序之数组如[1, 2, 3, 4, 5]若自左而右行nums[i-1]恒小于或等于nums[i]无"滴"无"降"于值。

今，思一旋转已排序之数组：[3, 4, 5, 1, 2]。
若扫描此，则见：

3 <= 4(甚好)
4 <= 5（善）
5 > 1（噫！此降之迹也！）
1 <= 2（善）

察之，唯一处，非递增之序有阙：5继1是也。此“阙”即回转之所在！诸元[1, 2]自首移于尾，遂成此值之独降。

若复有二之降？譬如[2, 1, 3, 4]。

2 > 1（降一）
1 <= 3（可）
3 <= 4（可）此独降耳。环之何如？4 > 2？非也。实则，若原数组本为[1,2,3,4]者，若旋转之，则必不得[2,1,3,4]。一旋转之，则尽旋转点后之元素，皆小于尽旋转点前之元素。唯一之“断”，唯在旋转点耳。

故其核心之悟，在于是也。排序旋转之数组，遍历其中，至多有一"降"（nums[i-1] > nums[i]）。

然，何谓回环？
思[4, 5, 1, 2, 3]。
4 <= 5（可）
5 > 1（降！）
1 <= 2（可）
2 <= 3（可）
于此，有一降。然亦，nums[n-1]（此即）3小于nums[0]（即4），此较亦为排序之"断"，概念上绕数组而行。吾等下降之数需计及此。

修订之悟：计nums[i-1] > nums[i]之数。此数当至多一，含之。 首尾相衔之较也。

步步为营法 🚶‍♂️

吾等当将此直觉凝为明法：

置一计数器： 吾需一变量，名曰 descentCount，设其值为 0。此计数器将记吾等得 nums[i-1] > nums[i] 之数。
遍历数组： 自第二元素起至数组末尾循环：i = 1。nums.size() - 1。
- 每次迭代，较当前元素与前者：nums[i]、nums[i-1]。
- 若nums[i-1] > nums[i]，则知已得“降序”或非递增之断。增之descentCount.
察回环之例： 循环既毕，当思末者与首者之相接。若数组有旋，则末者或胜首者（如[3, 4, 5, 1, 2]之例）。nums[4]（即2）小于nums[0]（即3）。此非增降之由。
然[1,2,3]（零回转）中，nums[2]（三）大于nums[0]（一）。
重审之：增降之迹，在序列递减处。
- [3, 4, 5, 1, 2]> 5 > 1(一脉)
  - nums[n-1]（二）是不可。逾之nums[0](三)。
- [1, 2, 3]->无后嗣。
  - nums[n-1]（三）是非也逾之nums[0](1).
- [2, 1, 3, 4]-> 2 > 1(一降)
  - nums[n-1](四)是非也逾之nums[0](二)。
吾之理路，于解法代码中环检之理也if (nums[n-1] > nums[0])吾辈当以例证溯其本源。
- [3,4,5,1,2]（n=五）
  - 循环(5 > 1)-> descentCount = 1
  - 回环nums[4] (2) > nums[0] (3) 者乃 false。
  - 总计 descentCount = 1。返 true。确。

*   `[2,1,3,4]` (n=4)
    *   Loop: `(2 > 1)` -> `descentCount = 1`
    *   Wrap-around: `nums[3]` (4) `>` `nums[0]` (2) is `true`. -> `descentCount = 2`.
    *   Total `descentCount = 2`. Return `false`. Correct. (Because original `[1,2,3,4]` cannot be rotated to `[2,1,3,4]`. It has two "breaks" if you consider it circular: `2->1` and `4->2` (conceptual circular link)).

*   `[1,2,3]` (n=3)
    *   Loop: No descents. `descentCount = 0`.
    *   Wrap-around: `nums[2]` (3) `>` `nums[0]` (1) is `true`. -> `descentCount = 1`.
    *   Total `descentCount = 1`. Return `true`. Correct. (A sorted array is considered a 0-rotated sorted array).

This wrap-around check for `nums[n-1] > nums[0]` cleverly handles the case where the "rotation point" effectively exists between the last and first element *if the array was originally sorted*. If `[1,2,3]` is seen as `1,2,3,1` (circular), then `3 > 1` is a descent. This means a perfectly sorted array will register 1 descent with this method.

终检： 经数组遍历及回环检查，若 descentCount 不大于1，此乃数组之意也本可也已排序且已旋转。返true否则，若descentCount大于1此谓排序之序中"断"处过多，非单次旋转之有序数组也。当返。false.

示吾码！💻

此逻辑之C++实现如是：

#include <vector> // Don't forget to include necessary headers!
#include <iostream> // For potential testing, though not strictly part of the solution

class Solution {
public:
    bool check(std::vector<int>& nums) {
        int count = 0; // Initialize descent counter
        int n = nums.size(); // Get the size of the array

        // Iterate from the second element to compare with the previous
        for (int i = 1; i < n; i++) {
            // If the previous element is greater than the current, it's a descent
            if (nums[i-1] > nums[i]) {
                count++;
            }
        }

        // Handle the wrap-around case: compare the last element with the first
        // If nums[n-1] is greater than nums[0], it means a "descent" occurs
        // conceptually between the end and the beginning of the array.
        // E.g., for [1,2,3], nums[2](3) > nums[0](1) is true.
        // For [3,4,5,1,2], nums[4](2) > nums[0](3) is false.
        if (nums[n-1] > nums[0]) {
            count++;
        }

        // A sorted and rotated array can have at most one "descent" (break).
        // This includes the wrap-around check, meaning a perfectly sorted array
        // will result in count = 1 due to the wrap-around check.
        return count <= 1;
    }
};

复杂度分析 ⏱️🚀

令 N 为 nums 数组中元素之数。

时间复杂度：O(N)
- 吾遍历数组一次于for 之循环，历 O(N) 之时。
- 其余诸务（初始化、size() 之唤、终较）皆需常时，O(1)。
- 是故，总时复杂，为 O(N) 所主。此甚效也，盖惟遍历数组一次耳。
空间复杂：O(1)
- 吾等仅用数个变量(count, n, i)以存吾之状，无论输入之数组大小如何。
- 并无辅助之数据结构（如新数组或哈希表）随输入之大小而增。
- 是以，空间之复杂度恒定，O(1)。

要旨熠熠✨

察"折处"之理： 至要之见，乃排序旋转之数列，最多仅有一处非递增之序被破。
回环之难： 勿忘末元与首元之关联！此乃多解谬误之由。吾法恰将此视作又一"降势"之候。
简则优：此题或诱君以繁杂之排序或数组操作，然单次遍历与计数，实为至简至效之解。

此法洁净，高效，且显君对数组性质之精妙理解！勤习之，不日即可通晓此道。乐书于码！

作者之户： 梵施廿七壹零
发表时间： 丙申年四月廿三子时二刻五十四分

推薦訂閱源

DEV Community