แบ่งอาร์เรย์ออกเป็นลำดับที่เพิ่มขึ้นใน Python

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

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1,2,2,3,3,4,4], K =3 ผลลัพธ์จะเป็นจริง เนื่องจากอาร์เรย์นี้สามารถแบ่งออกเป็นสองส่วนย่อย เช่น [1, 2,3,4] และ [2,3,4] มีความยาวอย่างน้อยอย่างละ 3 ครั้ง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• d :=แผนที่ใหม่

• ต้องการ :=0

• สำหรับแต่ละ i ใน nums ทำ

  • ถ้าฉันไม่อยู่ใน d ก็ไม่เท่ากับศูนย์ แล้ว

    • d[i]:=1

  • มิฉะนั้น

    • d[i] :=d[i] + 1

  • req :=สูงสุดของ req, d[i]

• คืนค่า จริง เมื่อ req*K <=ขนาดของ nums

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

ตัวอย่าง

คลาส Solution(object):def canDivideIntoSubsequences(self, nums, K):d ={} req =0 for i in nums:if i not in d:d[i]=1 else:d[i]+ =1 req =max(req,d[i]) return req*K<=len(nums)ob =Solution()print(ob.canDivideIntoSubsequences([1,2,2,3,3,4,4], 3))

อินพุต

ผลลัพธ์

จริง