ช่วงย่อยที่ไม่เรียงลำดับสั้นที่สุดใน Python

ภาพรวมปัญหา

ให้อาร์เรย์จำนวนเต็ม ต้องการหาช่วงย่อย (subarray) ที่ต่อเนื่องกัน เพียงช่วงเดียว ซึ่งถ้าจัดเรียงช่วงนั้นตามลำดับน้อยไปมาก อาร์เรย์ทั้งหมดจะเรียงลำดับได้ ต้องการหาความยาวของช่วงย่อยที่สั้นที่สุด

ตัวอย่าง: อาร์เรย์ [2,6,4,8,10,9,15] ช่วงที่ไม่เรียงคือ [6,4,8,10,9] ความยาว = 5

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

1. สร้างอาร์เรย์ res จากการเรียงลำดับ nums
2. สร้างลิสต์ r เก็บ index ที่ค่าไม่ตรงกันระหว่าง nums และ res
3. วนลูปทุก index ถ้า nums[i] != res[i] ให้เพิ่ม i เข้า r
4. ถ้า r ว่าง คืน 0; ถ้ามี 1 ค่า คืน 1
5. คืนค่า r[-1] - r[0] + 1 (ความยาวช่วง)

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

class Solution(object):
    def findUnsortedSubarray(self, nums):
        res = sorted(nums)
        r = []
        for i in range(len(res)):
            if nums[i] != res[i]:
                r.append(i)
        if not len(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