Permutation ก่อนหน้าด้วยการสลับครั้งเดียว (Previous Permutation With One Swap) ใน Python

โจทย์: กำหนดอาร์เรย์ A หา permutation ที่เล็กกว่า A น้อยที่สุด (lexicographically largest but smaller) ที่ทำได้ด้วยการสลับ 2 ตัวเลขครั้งเดียว หาไม่ได้คืนค่าเดิม

ตัวอย่าง

Input: [3,2,1]
Output: [3,1,2] (สลับ 2 และ 1)

อัลกอริทึม

1. หา left ตัวสุดท้ายที่ A[left] > A[left+1] (scan จากขวา)
2. หา right ตัวที่ A[right] < A[left] และมากที่สุด (closest smaller)
3. สลับ A[left] และ A[right]

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

class Solution(object):
    def prevPermOpt1(self, A):
        n = len(A)
        
        # หา left: จุดที่เริ่มลดลงจากขวา
        left = -1
        for i in range(n - 2, -1, -1):
            if A[i] > A[i + 1]:
                left = i
                break
        
        if left == -1:
            return A  # เรียงเพิ่มอยู่แล้ว ไม่มี permutation ก่อนหน้า
        
        # หา right: ค่าที่ < A[left] และมากที่สุด
        max_val = -1
        right = -1
        for i in range(left + 1, n):
            if A[i] < A[left] and A[i] > max_val:
                max_val = A[i]
                right = i
        
        # สลับ
        A[left], A[right] = A[right], A[left]
        return A

# ทดสอบ
ob = Solution()
print(ob.prevPermOpt1([4,2,3,1,3]))  # Output: [4, 2, 1, 3, 3]

ตัวอย่าง Input/Output

Input: [4,2,3,1,3]
Output: [4, 2, 1, 3, 3]

ความซับซ้อน: Time O(n), Space O(1)