โจทย์
มีอาร์เรย์ nums ต้องตรวจสอบว่ามันเคยถูกเรียงลำดับ Non-decreasing แล้วหมุน (Rotate) ไปจำนวนหนึ่ง (อาจ 0) หรือไม่ อาจมีค่าซ้ำได้
ตัวอย่าง: nums = [12,15,2,5,6,9] → True (หมุนขวา 2 ตำแหน่ง จาก [2,5,6,9,12,15])
อัลกอริธึม
- หาจุดที่ลำดับแตก (หา
jที่nums[j] > nums[j+1]) - รวม Subarray หลังจุดแตก + Subarray ก่อนจุดแตก →
res - ตรวจสอบ
resว่าเรียง Non-decreasing ทั้งหมดหรือไม่
โค้ด 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)) # Output: True
Input / Output
Input: [12,15,2,5,6,9]
Output: True
