Tìm số mảng con trong hoán vị của N số tự nhiên đầu tiên sao cho trung vị của chúng là M trong Python

Giả sử chúng ta có một mảng A chứa hoán vị của N số tự nhiên đầu tiên và một số M khác cũng được cho trước, trong đó M ≤ N, chúng ta phải tìm số mảng con sao cho trung vị của dãy là M. Như chúng ta đã biết trung vị của một dãy được định nghĩa là giá trị của phần tử ở giữa dãy sau khi sắp xếp theo thứ tự tăng dần. Đối với chuỗi độ dài chẵn, bên trái của hai phần tử ở giữa được sử dụng.

Vì vậy, nếu đầu vào là A =[3, 5, 6, 4, 2] và M =5, thì đầu ra sẽ là 4 vì các mảng con được yêu cầu là [3, 5, 6], [5], [5 , 6] và [5, 6, 4].

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• n:=kích thước của arr

• my_map:=một bản đồ mới

• my_map [0]:=1

• có:=Sai, thêm:=0, kết quả:=0

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • nếu arr [i]

    • add:=add - 1

  • ngược lại khi arr [i]> m thì

    • thêm:=thêm + 1

  • nếu arr [i] giống với m thì

    • có:=True

  • nếu có là đúng, thì

    • nếu thêm hiện tại vào my_map, thì

      • kết quả:=result + my_map [thêm]

    • nếu add-1 hiện diện trong my_map, thì

      • kết quả:=result + my_map [add - 1]

  • nếu không,

    • my_map [add]:=(giá trị của my_map [add], nếu có, nếu không thì 0) + 1

• trả về kết quả

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[3, 5, 6, 4, 2] , 5

Đầu ra

3