{"id":8079,"date":"2021-02-07T08:07:02","date_gmt":"2021-02-07T16:07:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8079"},"modified":"2021-02-07T08:07:57","modified_gmt":"2021-02-07T16:07:57","slug":"leetcode-1752-check-if-array-is-sorted-and-rotated","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1752-check-if-array-is-sorted-and-rotated\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1752. Check if Array Is Sorted and Rotated"},"content":{"rendered":"\n

Given an array nums<\/code>, return true<\/code> if the array was originally sorted in non-decreasing order, then rotated some<\/strong> number of positions (including zero)<\/em>. Otherwise, return false<\/code>.<\/p>\n\n\n\n

There may be duplicates<\/strong> in the original array.<\/p>\n\n\n\n

Note:<\/strong> An array A<\/code> rotated by x<\/code> positions results in an array B<\/code> of the same length such that A[i] == B[(i+x) % A.length]<\/code>, where %<\/code> is the modulo operation.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [3,4,5,1,2]\nOutput:<\/strong> true\nExplanation:<\/strong> [1,2,3,4,5] is the original sorted array.\nYou can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [2,1,3,4]\nOutput:<\/strong> false\nExplanation:<\/strong> There is no sorted array once rotated that can make nums.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [1,2,3]\nOutput:<\/strong> true\nExplanation:<\/strong> [1,2,3] is the original sorted array.\nYou can rotate the array by x = 0 positions (i.e. no rotation) to make nums.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [1,1,1]\nOutput:<\/strong> true\nExplanation:<\/strong> [1,1,1] is the original sorted array.\nYou can rotate any number of positions to make nums.\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [2,1]\nOutput:<\/strong> true\nExplanation:<\/strong> [1,2] is the original sorted array.\nYou can rotate the array by x = 5 positions to begin on the element of value 2: [2,1].\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 100<\/code><\/li>
  • 1 <= nums[i] <= 100<\/code><\/li><\/ul>\n\n\n\n
    Solution: Counting and checking<\/strong><\/h2>\n\n\n\n
    Count how many turning points (nums[i] < nums[i – 1]) in the array. Return false if there are more than 1.
    For the turning point r, (nums[r] < nums[r – 1), return true if both of the following conditions are satisfied: 
    1. nums[r – 1] is the largest number, e.g. nums[r – 1] >= nums[n – 1]
    2. nums[r] is the smallest number, e.g. nums[r] <= nums[0]<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool check(vector& nums) {\n    int count = 0;\n    int r = -1;\n    for (size_t i = 1; i < nums.size(); ++i)\n      if (nums[i] < nums[i - 1]) {\n        ++count;\n        r = i;\n      }\n    if (count == 0) return true;\n    if (count > 1) return false;     \n    return nums[r] <= nums[0] && nums[r - 1] >= nums.back();\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false. There may be duplicates in the original…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[222,367],"class_list":["post-8079","post","type-post","status-publish","format-standard","hentry","category-array","tag-easy","tag-rotation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8079","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8079"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8079\/revisions"}],"predecessor-version":[{"id":8082,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8079\/revisions\/8082"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8079"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8079"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8079"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}