วิธีตรวจสอบว่า Array ใกล้จะเรียงลำดับแล้ว (Almost Sorted) ใน Python

ปัญหา

Array เรียกว่า "Almost Sorted" หากทุกตัวเลขอยู่ห่างจากตำแหน่งที่ถูกต้องใน Array ที่เรียงแล้วไม่เกิน 1 ตำแหน่ง

ตัวอย่าง: [10, 30, 20, 40] → True (10 อยู่ถูกต้อง, 30 และ 20 สลับกัน, 40 ถูกต้อง)

แนวทางแก้ปัญหา

1. ลูปผ่าน Array หากพบ nums[i] > nums[i+1] ให้สลับแล้วข้าม index ถัดไป
2. หลังจบลูป ตรวจสอบอีกครั้งว่ามีค่าผิดปกติเหลือหรือไม่

ตัวอย่างโค้ด

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

nums = [10, 30, 20, 40]
print(solve(nums))  # True

อินพุต / เอาต์พุต

Input: [10, 30, 20, 40]
Output: True