Chương trình kiểm tra mảng có được sắp xếp và xoay không trong Python

Giả sử ta có mảng nums, ta phải kiểm tra xem mảng này có ban đầu được sắp xếp theo thứ tự không giảm và sau đó bị xoay một số vị trí (có thể là 0) hay không. Mảng có thể chứa phần tử trùng lặp.

Ví dụ: nums = [12,15,2,5,6,9], kết quả là True, vì nó bị xoay phải 2 vị trí.

Giải thuật

1. j := 0
2. While j < len(nums) - 1 và nums[j] <= nums[j + 1]: j++
3. res := nums[j+1:] + nums[:j+1] (ghép lại mảng sau khi xoay ngược)
4. For i từ 0 đến len(res) - 1:
   • Nếu res[i] > res[i + 1]: trả về False
5. Trả về True

Ví dụ (Python)

def solve(nums):
    j = 0
    while j < len(nums) - 1 and nums[j] <= nums[j + 1]:
        j += 1
    res = nums[j + 1:] + nums[:j + 1]
    for i in range(len(res) - 1):
        if res[i] > res[i + 1]:
            return False
    return True

nums = [12, 15, 2, 5, 6, 9]
print(solve(nums))

Input

[12,15,2,5,6,9]

Output

True