প্রথম N প্রাকৃতিক সংখ্যার পারমুটেশনে সাব অ্যারেগুলির সংখ্যা খুঁজে বের করুন যেমন পাইথনে তাদের মধ্যক হল M

ধরুন আমাদের কাছে একটি অ্যারে রয়েছে যেখানে প্রথম 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 এর মত হয়, তাহলে
  - আছে :=সত্য
- যদি সত্য হয়, তাহলে
  - যদি my_map-এ বর্তমান যোগ করুন, তাহলে
    - ফলাফল :=ফলাফল + আমার_ম্যাপ[যোগ করুন]
  - যদি my_map-এ add-1 উপস্থিত থাকে, তাহলে
    - ফলাফল :=ফলাফল + আমার_ম্যাপ[যোগ - 1]
- অন্যথায়,
  - my_map[add] :=(my_map[add] এর মান, যদি উপস্থিত থাকে, অন্যথায় 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