This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact

describe

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 array.

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

Example 1:

Input: nums = [3,4,5,1] Output: true Explanation: [1,2,3,4,5] is the original sorted array. You can rotate the array by x = 3 positions to begin on the element of The value of 3:,4,5,1,2 [3].Copy the code

Example 2:

Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.
Copy the code

Example 3:

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.
Copy the code

Example 4:

Input: nums = [1,1,1]
Output: true
Explanation: [1,1,1] is the original sorted array.
You can rotate any number of positions to make nums.
Copy the code

Example 5:

Input: nums = [2,1] Output: true Explanation: [1,2] is the original sorted array. You can rotate the array by x = 5 positions to begin on the element of value 2: (2, 1].Copy the code

Note:

1 <= nums.length <= 100
1 <= nums[i] <= 100
Copy the code

parsing

If nums is truncated from a certain position, then the two parts are interchanged and spliced together, the result is a non-descending list (ascending or fully equal list). Nums [I :] + nums[: I] = TMP; nums[: I] = TMP; Returns True if it is equal, and finally False if it is not.

answer

class Solution(object):
    def check(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        tmp = sorted(nums)
        if nums == tmp:
            return True
        for i in range(1,len(nums)):
            if nums[i:] + nums[:i] == tmp:
                return True
        return False
            	      
		
Copy the code

The results

The value of the linked list with Python online submissions Is assessed with a value of 700 ms. 13.5 MB, less than 33.33% of Python online submissions for Check if Array Is Sorted and Rotated.Copy the code

parsing

There is another way of thinking, that is to find the rule, there are two cases of ascending and full equality in non-descending order, then:

  • If nums=[3,4,5,1,2] really can be transformed into a non-descending list [1,2,3,4,5], then there must be only one index I that causes nums[I]>nums[I +1], in this case index 2
  • If nums=[1,1,1] or nums=[1,2,3], there is no index that would cause nums[I]> NUMs [I +1]
  • If nums=[2,1,3,4], even though there is only one index I that causes nums[I]>nums[I +1], the resulting list [1,3,4,2] is not non-descending because nums[0]

So the idea is clear:

  • Count counts the number of occurrences of nums[I]
  • Return False if count is greater than 1
  • Return True if count==0 or nums[0]>=nums[-1], False otherwise

answer

class Solution(object):
    def check(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        count = 0
        for i in range(1,len(nums)):
            if nums[i-1]>nums[i]:
                count+=1
                if count>1:
                    return False
        return count==0 or nums[0]>=nums[-1]
Copy the code

The results

The value of the collected data in the linked list Is Sorted with a value of 700 ms. 13.5 MB, less than 12.15% of Python online submissions for Check if Array Is Sorted and Rotated.Copy the code

Original link: leetcode.com/problems/ch…

Your support is my biggest motivation