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

मान लीजिए हमारे पास एक ऐरे 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 := len(arr)
• my_map := {}
• my_map[0] := 1
• has := False, add := 0, result := 0
• i को 0 से n-1 तक के लिए:
  • यदि arr[i] < m, तो add := add - 1
  • अन्यथा यदि arr[i] > m, तो add := add + 1
  • यदि arr[i] == m, तो has := True
  • यदि has true है:
    • यदि add my_map में मौजूद है, तो result := result + my_map[add]
    • यदि add-1 my_map में मौजूद है, तो result := result + my_map[add - 1]
  • अन्यथा:
    • my_map[add] := my_map.get(add, 0) + 1
• result लौटाएं।

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

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