पहले N प्राकृतिक संख्याओं के क्रमचय में उप सरणियों की संख्या ज्ञात करें जैसे कि उनका माध्यिका M पायथन में है

मान लीजिए कि हमारे पास एक सरणी A है जिसमें पहले N प्राकृतिक संख्याओं का क्रमचय है और दूसरी संख्या M भी दी गई है, जहाँ M ≤ N, हमें उप-सरणी की संख्या ज्ञात करनी होगी जैसे कि अनुक्रम का माध्यक M है। जैसा कि हम जानते हैं कि किसी अनुक्रम के माध्यिका को उस तत्व के मान के रूप में परिभाषित किया जाता है जो आरोही क्रम के अनुसार क्रमबद्ध करने के बाद अनुक्रम के बीच में होता है। सम लंबाई अनुक्रम के लिए, दो मध्य तत्वों के बाईं ओर का उपयोग किया जाता है।

इसलिए, यदि इनपुट ए =[3, 5, 6, 4, 2] और एम =5 की तरह है, तो आउटपुट 4 होगा क्योंकि आवश्यक उप-सरणी हैं [3, 5, 6], [5], [5 , 6] और [5, 6, 4]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=गिरफ्तारी का आकार

• my_map :=एक नया नक्शा

• my_map[0] :=1

• है :=असत्य, जोड़ें :=0, परिणाम :=0

• मेरे लिए 0 से n की सीमा में, करें

  • अगर गिरफ्तारी [i] <मी, फिर

    • जोड़ें:=जोड़ें - 1

  • अन्यथा जब arr[i]> m, तब

    • जोड़ें:=+ 1 जोड़ें

  • अगर गिरफ्तारी [i] एम के समान है, तो

    • है :=सच

  • अगर है सच है, तो

    • अगर my_map में मौजूद जोड़ें, तो

      • परिणाम:=परिणाम + my_map[जोड़ें]

    • अगर my_map में ऐड-1 मौजूद है, तो

      • परिणाम :=परिणाम + my_map[add - 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

आउटपुट

3