การเปลี่ยนแปลงก่อนหน้าด้วย One Swap ใน Python

สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็มบวก (ไม่จำเป็นต้องซ้ำกัน) เราต้องหาการเรียงสับเปลี่ยนที่ใหญ่ที่สุดทางศัพท์ที่เล็กกว่า A ซึ่งสามารถทำได้ด้วยการสลับหนึ่งครั้ง (การแลกเปลี่ยน A จะแลกเปลี่ยนตำแหน่งของตัวเลขสองตัว A[i] และ อ[j]). หากเป็นไปไม่ได้ ให้คืนค่าอาร์เรย์เดิม ดังนั้นหากอาร์เรย์เป็นแบบ [3,2,1] ผลลัพธ์จะเป็น [3,1,2] โดยสลับ 2 กับ 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A
• สำหรับด้านซ้ายในช่วง n – 2 ลงไป -1
  • ถ้าเหลือ =-1 ให้คืนค่า A ไม่เช่นนั้นเมื่อ A[left]> A[left + 1] แตก
• องค์ประกอบ :=0, ดัชนี :=0
• สำหรับขวาในช่วง ซ้าย + 1 ถึง n
  • ถ้า A[right] องค์ประกอบ แล้ว
    • องค์ประกอบ =A[ขวา]
    • ดัชนี :=ขวา
• สลับ A[ซ้าย] และ A[ดัชนี]
• คืน A

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution(object):
   def prevPermOpt1(self, A):
      n = len(A)
      for left in range(n-2,-2,-1):
         if left == -1:
            return A
         elif A[left]>A[left+1]:
            break
      element = 0
      index = 0
      for right in range(left+1,n):
         if A[right]<A[left] and A[right]>element:
            element = A[right]
            index = right
      temp = A[left]
      A[left] = A[index]
      A[index] = temp
      return A
ob = Solution()
print(ob.prevPermOpt1([4,2,3,1,3]))

อินพุต

[4,2,3,1,3]

ผลลัพธ์

[4, 2, 1, 3, 3]