สมมติว่าเรามีอาร์เรย์ A ที่มีการเรียงสับเปลี่ยนของตัวเลขธรรมชาติ N ตัวแรกและให้หมายเลข M อีกตัวหนึ่ง โดยที่ M ≤ N เราต้องหาจำนวนอาร์เรย์ย่อยที่ ค่ามัธยฐานของลำดับคือ M ดังที่เราทราบค่ามัธยฐานของลำดับถูกกำหนดให้เป็นค่าขององค์ประกอบที่อยู่ตรงกลางของลำดับหลังจากจัดเรียงตามลำดับจากน้อยไปมาก สำหรับลำดับที่มีความยาวเท่ากัน จะใช้ด้านซ้ายขององค์ประกอบตรงกลางสองส่วน
ดังนั้น หากอินพุตเป็น A =[3, 5, 6, 4, 2] และ M =5 เอาต์พุตจะเป็น 4 เนื่องจากอาร์เรย์ย่อยที่ต้องการคือ [3, 5, 6], [5], [5 , 6] และ [5, 6, 4].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ arr
-
my_map :=แผนที่ใหม่
-
my_map[0] :=1
-
มี :=เท็จ เพิ่ม :=0, ผลลัพธ์ :=0
-
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
-
ถ้า arr[i]
-
เพิ่ม :=เพิ่ม - 1
-
-
มิฉะนั้นเมื่อ arr[i]> m แล้ว
-
เพิ่ม :=เพิ่ม + 1
-
-
ถ้า arr[i] เหมือนกับ m แล้ว
-
มี :=จริง
-
-
ถ้ามีจริงแล้ว
-
ถ้าเพิ่ม present ใน my_map แล้ว
-
ผลลัพธ์ :=ผล + my_map[เพิ่ม]
-
-
ถ้า add-1 มีอยู่ใน my_map แล้ว
-
ผลลัพธ์ :=ผล + my_map[เพิ่ม - 1]
-
-
-
มิฉะนั้น
-
my_map[เพิ่ม] :=(ค่าของ my_map[เพิ่ม] หากมี มิฉะนั้น 0) + 1
-
-
-
ส่งคืนผลลัพธ์
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(arr, m):
n = len(arr)
my_map = {}
my_map[0] = 1
has = False
add = 0
result = 0
for i in range(n):
if (arr[i] < m):
add -= 1
elif (arr[i] > m):
add += 1
if (arr[i] == m):
has = True
if (has):
if(add in my_map):
result += my_map[add]
if add-1 in my_map:
result += my_map[add - 1]
else:
my_map[add] = my_map.get(add, 0) + 1
return result
arr = [3, 5, 6, 4, 2]
m = 5
print(solve(arr, m)) อินพุต
[3, 5, 6, 4, 2] , 5
ผลลัพธ์
3
