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

题目描述

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 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

方法一：我的解法

class Solution {
public:
    bool check(vector<int>& nums) {
        int pos = 0;
        int n = nums.size();
        vector<int> numsOrigin(n);

        // 保存默认数组
        for(int i=0; i<n ; i++)
            numsOrigin[i] = nums[i];
            
        // nums为原数组 
        sort(nums.begin(), nums.end()); // 默认升序

		// 确定目标元素的偏移量
        for(int i=0; i<n; i++){
            // 条件1:当前数字与原数组不匹配
            // 条件2:如果有若干连续的数字，考虑最后一个
            if(numsOrigin[i] != nums[i] && numsOrigin[i] != numsOrigin[(i+1) % n]){
                // 目标元素
                int flag = numsOrigin[i];
                for(int j=0; j<n; j++){
                    // 条件1:在排序数组中找到目标元素
                    // 条件2:如果有若干连续数字，考虑最后一个
                    if(flag == nums[j] && nums[j] != nums[(j + 1)%n]){
                        // 确定偏移位置
                        pos = (j - i + n) % n; 
                        break;
                    }
                }
                break;
            }
        }
        for(int i=0; i<n; i++){
            if(numsOrigin[i] != nums[(i + pos) % n])   return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

方法二：优秀题解

class Solution {
public:
    bool check(vector<int>& nums) {
        int cnt = 0; // 记录非递增情况出现的次数
        int n = nums.size();
        for(int i=0; i<n-1; i++){
            if(nums[i] > nums[i+1]) cnt ++;
        }
        // nums已经是非递减数组，说明与原数组相同
        if(cnt == 0)    return true;
        // 仅发生了一次非递增
        // 并且第一个元素大于最后一个元素，说明首尾元素也是非递减的
        else if(cnt == 1 && nums[0] >= nums[n-1])   return true;
        // 不止一次非递增
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

心得

• 这道题是11.27的每日一题，那天出去玩了，没做出来，今天补一下。这道题是简单题，但我的解法略微显得复杂，甚至我提交了很多次，最后在卡测试点才通过的，但是还是记录一下，更推荐看解法二。

• 解法一：常规解法

• 思路：由于 原数组是一个 递增 数组，因此我对 nums 进行了 sort 排序得到了原数组，之后就是确定一个 目标元素 ，确定目标元素在 「给定数组」 和 「原数组」之间的偏移量，最后在给定数组中遍历偏移量即可。

• 重点在于 如何确定 目标元素 和 偏移量？

  • 一开始我只考虑到了 条件1：找到第一个在「原数组」和「给定数组」中不同的元素。
    但是这个考虑不全面， 比如：
    • nums = [4, 5, 7, 7, 9, 9, 10, 10, 3, 4]，
      这个数组的原数组是 [3, 4, 4, 5, 7, 7, 9, 9, 10, 10]
    • 第一个不同的元素是 nums 中的第一个 4 ，但是很明显，我们可以发现第一个 4 应该对应的是 原数组中的第二个 4，然而我一开始给出的条件只能将第一个 4 对应到 原数组的第一个 4。
  • 因此，我在确定偏移量的部分加上了 条件2：如果有若干连续的数字，考虑最后一个。
    此时，上面的例子就能正确通过了，我们也确定了 目标元素。
  • 然而此时出现另外一种情况，比如：
    • nums = [5，5，6，6，6，9，1，2]，
      这个数组的原数组是 [1，2，5，5，6，6，6，9]
    • 第一个不同的元素应该是 第一个 5 ， 如果按照上面的两个逻辑，此时的第一个 5 会默认匹配到最后一个 5 ，那显然是不正确的，因此我在确定目标元素的部分加上了 条件2：如果有若干连续的数字，考虑最后一个。此时，这个例子的目标元素就是第二个 5 。

  综上所述，通过各两个条件，我们就能确定目标元素和偏移量。

• 方法二：
• 思路：对于 True，其实有两种情况：
  • 情况一： 如果给定数组已经是递增的，说明原数组轮转 0 个位置就可以得到给定数组；
  • 情况二： 如果在 nums 数组中，仅仅有一次「非递增」的情况发生，那么需要满足 nums[0] >= nums[nums.length -1]

参考资料：

1. 【爪哇缪斯】图解LeetCode