Giả sử chúng ta có một mảng n giá trị duy nhất. Cần kiểm tra xem mảng này có được sắp xếp và xoay ngược chiều kim đồng hồ hay không. Ở đây yêu cầu ít nhất một lần xoay, nên mảng đã sắp xếp hoàn toàn không được coi là đã sắp xếp và xoay.
Ví dụ, nếu đầu vào là nums = [4,5,6,8,1,3], thì đầu ra sẽ là True vì xoay 2 lần theo chiều kim đồng hồ sẽ được mảng sắp xếp [1, 3, 4, 5, 6, 8].
Các bước giải quyết:
- min_element := phần tử nhỏ nhất của nums.
- min_index := chỉ số của min_element trong nums.
- before_sorted := True.
- Duyệt i từ 1 đến min_index - 1:
- Nếu nums[i] < nums[i-1], before_sorted := False, thoát vòng lặp.
- after_sorted := True.
- Duyệt i từ min_index + 1 đến size - 1:
- Nếu nums[i] < nums[i-1], after_sorted := False, thoát vòng lặp.
- Nếu before_sorted và after_sorted đều True và nums[-1] < nums[0], trả về True.
- Ngược lại, trả về False.
Xem ví dụ dưới đây để hiểu rõ hơn:
Ví dụ
def solve(nums):
min_element = min(nums)
min_index = nums.index(min_element)
before_sorted = True
for i in range(1, min_index):
if nums[i] < nums[i - 1]:
before_sorted = False
break
after_sorted = True
for i in range(min_index + 1, len(nums)):
if nums[i] < nums[i - 1]:
after_sorted = False
break
if before_sorted and after_sorted and nums[-1] < nums[0]:
return True
else:
return False
nums = [4,5,6,8,1,3]
print(solve(nums))
Đầu vào
[4,5,6,8,1,3]
Đầu ra
True