Keshawn_lu's Blog

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

数组
字数统计: 354阅读时长: 1 min
2022/11/27 Share

题目简介：

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

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

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

注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。

示例 1：

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

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

思路：

首先判断数组本身是否已经是按非递减顺序排列的了，如果是，直接返回true。

否则，判断是否存在两个及以上的转折点（即nums[i + 1] < nums[i]），如果整个数组存在两个及以上的转折点，则返回false。

其中nums[nums.size() - 1] > nums[0]也算转折点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool check(vector<int>& nums) {

        int i = 0;
        while(i + 1 < nums.size() && nums[i] <= nums[i + 1])
            i++;
        
        i++;

        if(i == nums.size())
            return true;

        while(i + 1 < nums.size()){

            if(nums[i] > nums[i + 1])
                return false;

            i++;
        }

        return nums[nums.size() - 1] <= nums[0];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网