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

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม เราจำเป็นต้องค้นหาอาร์เรย์ย่อยแบบต่อเนื่องหนึ่งรายการ ซึ่งหากเราจัดเรียงอาร์เรย์ย่อยนั้นในลำดับจากน้อยไปมาก อาร์เรย์ทั้งหมดก็จะถูกจัดเรียงด้วย เราต้องหาอาร์เรย์ย่อยที่สั้นที่สุดและส่งออกความยาว ดังนั้นหากอาร์เรย์คือ [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

ตัวอย่าง (Python)

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

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