每日一题 —— LC. 1752 检查数组是否经排序和轮转得到

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

给你一个数组 nums 。nums存在一个源数组中，其中所有元素与 nums 相同，但按非递减顺序排列。

如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。

源数组中可能存在 重复项 。

示例

输入：nums = [3,4,5,1,2]
输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。
1
2
3
4

思路

这是一道简单题，但特此记录一下。（下面用递增取代非递减的说法）

我自己的思路是：若要返回true

• 要么nums数组本身已经是递增顺序
• 要么nums能够被分成两半，左半部分递增，右半部分递增，且左半部分全部的值都大于等于右半部分全部的值

我自己的思路是遍历一次，尝试找到左右两半部分的分界点，并实时检查是否满足条件

class Solution {
public:
    bool check(vector<int>& nums) {
        int i = 1, n = nums.size();
        while (i < n && nums[i] >= nums[i - 1]) i++;
        // 上面while循环结束后, i要么到达末尾, 要么是指向右半部分第一个位置
        while (i < n) {
            // 如果进入这个while循环, 说明是能够分成两半的这种情况
            // 这右半部分, 需要满足
            // 1.每个数都必须小于等于左半部分的最小的数(nums[0])
            // 2.每相邻两个数之间应该递增
            // 上述2点只要不满足其一, 就可以return false了
            if (nums[i] > nums[0]) return false;
            if (i + 1 < n && nums[i + 1] < nums[i]) return false;
            i++;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在评论区看到有这样一种做法是：统计递减顺序数对，只有递减的数对的数量小于等于1，才返回true。

我顿时心生疑虑，感觉这样不对啊！于是copy了下代码提交，发现竟然能通过。于是准备来找一下反例。结果发现这种做法是正确的。

class Solution {
public:
    bool check(vector<int>& nums) {
        // 统计递减元素的数量
        int cnt = 0, n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) cnt++;
        }
        return cnt <= 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11

在上面的第一种情况，nums整体递增时肯定是没问题的，递减元素的数量为0，主要是第二种情况，无疑在左右两半部分的交界处，存在一对递减元素，但仅存在这一对吗？首先左右两半部分区间内部肯定都是递增的，关键在于右半部分的最后一个数，和左半部分的第一个数，很明显，因为右半部分要整体小于左半部分，所以对于右半部分最后一个数，它肯定和左半部分第一个数也是递增关系，所以这种做法是正确的。

这种思路挺巧妙的，也很简单。特此记录