สมมติว่าเรามีอาร์เรย์ที่ไม่ได้จัดเรียง A[0..n-1] ขนาด n เราต้องหาความยาวต่ำสุดของอาร์เรย์ย่อย A[s..e] โดยการเรียงลำดับ อาร์เรย์ย่อยนี้ อาร์เรย์ทั้งหมดจะถูกจัดเรียง ดังนั้น หากอาร์เรย์เป็นแบบ [2,6,4,8,10,9,15] ผลลัพธ์จะเป็น 5 อาร์เรย์ย่อยจะเป็น [6,4,8,10,9]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
res :=จัดเรียง nums เป็นอาร์เรย์
-
ตอบ :=0
-
ตั้งค่า r เป็นรายการที่เชื่อมโยง
-
สำหรับผมอยู่ในช่วง 0 ถึงความยาวของความละเอียด
-
ถ้า nums[i] ไม่เหมือนกับ res[i] ให้ใส่ i เข้าไปใน r
-
-
ถ้าความยาวของ r เป็น 0, ให้คืนค่า 0, ถ้าความยาวของ r เป็น 1 ให้คืนค่า 1
-
คืนค่าองค์ประกอบสุดท้ายของ r – องค์ประกอบแรกของ r + 1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution(object): def findUnsortedSubarray(self, nums): res = sorted(nums) ans = 0 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
