หาสับอาร์เรย์ที่ไม่เรียงลำดับสั้นที่สุดซึ่งการเรียงจะทำให้อาร์เรย์ทั้งหมดเรียงลำดับใน Python

สมมติว่าเรามีอาร์เรย์ A ขนาด n ไม่เรียงลำดับ ต้องการหาสับอาร์เรย์ A[s..e] ที่สั้นที่สุด ซึ่งถ้าเรียงสับอาร์เรย์นี้แล้ว อาร์เรย์ทั้งหมดจะเรียงลำดับ

เช่น [2, 6, 4, 8, 10, 9, 15] ผลลัพธ์คือ 5 สับอาร์เรย์คือ [6, 4, 8, 10, 9]

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

1. สร้างอาร์เรย์ res โดยเรียงลำดับอาร์เรย์ต้นฉบับ
2. เปรียบเทียบแต่ละตำแหน่ง รวบรวมดัชนีที่ค่าต่างกัน
3. ถ้าไม่มีความต่าง คืนค่า 0; ถ้ามี 1 ตำแหน่ง คืนค่า 1
4. มิฉะนั้น คืนค่า last_index - first_index + 1

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

class Solution:
    def findUnsortedSubarray(self, nums):
        res = sorted(nums)
        r = []
        for i in range(len(res)):
            if nums[i] != res[i]:
                r.append(i)
        if not r:
            return 0
        if len(r) == 1:
            return 1
        return r[-1] - r[0] + 1

ob1 = Solution()
print(ob1.findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]))

อินพุต

[2, 6, 4, 8, 10, 9, 15]

เอาต์พุต

5