สมมติว่าเรามีลำดับของตัวเลข 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]