โปรแกรมหาสับลิสต์สั้นที่สุดที่เมื่อเรียงแล้วทั้งลิสต์จะเรียงใน Python

สมมติว่าเรามีรายการตัวเลขชื่อ nums เราต้องการหาความยาวของสับลิสต์ที่สั้นที่สุดใน nums ซึ่งถ้าเรียงสับลิสต์นั้น แล้วอาร์เรย์ทั้งหมด nums จะถูกเรียงในลำดับเพิ่มขึ้น

ตัวอย่าง

หากอินพุตคือ nums = [1,2,5,4,9,10] ผลลัพธ์จะเป็น 2 เนื่องจากการเรียงสับลิสต์ [5, 4] จะได้ [1, 2, 4, 5, 9, 10]

ขั้นตอนการแก้ปัญหา

1. f := -1, l := -1
2. lst := เรียงลำดับรายการ nums
3. ลูป i จาก 0 ถึงขนาดของ nums:
   • ถ้า nums[i] ไม่เท่ากับ lst[i]:
     • ถ้า f เป็น -1 ให้ f := i
     • อื่นๆ ให้ l := i
4. ถ้า l เป็น -1 และ f เป็น -1 ให้คืนค่า 0
5. คืนค่า l - f + 1

การใช้งาน

class Solution:
    def solve(self, nums):
        f = -1
        l = -1
        lst = sorted(nums)
        for i in range(len(nums)):
            if nums[i] != lst[i]:
                if f == -1:
                    f = i
                else:
                    l = i
        if l == -1 and f == -1:
            return 0
        return l - f + 1

ob = Solution()
print(ob.solve([1,2,5,4,9,10]))

อินพุต

[1,2,5,4,9,10]

เอาต์พุต

2