โปรแกรมตรวจสอบอาร์เรย์ย่อยสามารถจัดเรียงใหม่จากลำดับเลขคณิตหรือไม่ในPython

สมมติว่าเรามีลำดับของตัวเลข nums และอีกสองอาร์เรย์ l และ r ของขนาด m l และ r เหล่านี้แสดงถึงคิวรี่ช่วงเช่น [l[i], r[i]] เราต้องหาลำดับบูลีน ans โดยที่ ans[i] เป็นจริงเมื่อ subarray nums[l[i]], nums[l[i] + 1], ... nums[r[i] - 1], สามารถจัดเรียง nums[r[i]] เพื่อสร้างลำดับเลขคณิต มิฉะนั้น จะเป็นเท็จ

ลำดับเรียกว่าเลขคณิต ถ้าประกอบด้วยองค์ประกอบอย่างน้อยสององค์ประกอบ และความแตกต่างระหว่างทุกสององค์ประกอบที่ต่อเนื่องกันจะเหมือนกัน ตัวอย่างเช่น ลำดับเลขคณิตบางตัว ได้แก่ [2, 4, 6, 8, 10], [5, 5, 5, 5], [4, -2, -8, -14] แต่ไม่ใช่ [2, 2, 3, 6, 9].

ดังนั้น หากอินพุตเท่ากับ nums =[6,8,7,11,5,9], l =[0,0,2], r =[2,3,5] ผลลัพธ์จะเป็น [True , เท็จ, จริง] เพราะ −

• สำหรับแบบสอบถาม [0, 2] ลำดับคือ [6,8,7] สามารถจัดเรียงใหม่เป็น [6,7,8] สิ่งนี้ถูกต้อง

• สำหรับข้อความค้นหา [0, 3] ลำดับคือ [6,8,7,11] ไม่สามารถจัดเรียงใหม่ในลำดับเลขคณิตได้

• สำหรับข้อความค้นหา [2, 5] ลำดับคือ [7,11,5,9] สามารถจัดเรียงใหม่เป็น [5,7,9,11] ได้ ถูกต้อง

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

• ใหม่ :=รายการขนาดเท่ากับ l และเติมด้วยค่าจริงทั้งหมด

• สำหรับฉันในช่วง 0 ถึงขนาด l - 1 ทำ

  • data :=รายการย่อยของ nums จากดัชนี l[i] ถึง r[i]

  • จัดเรียงข้อมูลรายการ

  • d :=รายการใหม่

  • สำหรับ j ในช่วง 0 ถึงขนาดของข้อมูล - 2 ทำ

    • ใส่ข้อมูล[j+1] - data[j] ต่อท้าย d

  • d :=รายการใหม่จากชุดใหม่จาก d

  • ถ้าขนาดของ d ไม่เท่ากับ 1 แล้ว

    • ใหม่[i] :=เท็จ

• กลับมาใหม่

ตัวอย่าง

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

def solve(nums, l, r):
   new = [True]*len(l)

   for i in range(len(l)):
      data = nums[l[i]:r[i]+1]
      data.sort()

      d = []
      for j in range(len(data) - 1):
         d.append(data[j+1] - data[j])

      d = list(set(d))
      if len(d) != 1:
         new[i] = False
   return new

nums = [6,8,7,11,5,9]
l = [0,0,2]
r = [2,3,5]
print(solve(nums, l, r))

อินพุต

[6,8,7,11,5,9], [0,0,2], [2,3,5]

ผลลัพธ์

[True,False,True]