Python का उपयोग करके सर्कुलर ट्रैक में सबसे अधिक विजिट किया गया सेक्टर खोजें

मान लीजिए हमारे पास एक संख्या n और rounds नामक एक सरणी है। हमारे पास एक सर्कुलर ट्रैक है जिसमें n अलग-अलग सेक्टर हैं जो 1 से n तक लेबल किए गए हैं। अब इस ट्रैक पर एक दौड़ आयोजित की जाएगी, जिसमें m अलग-अलग राउंड होते हैं। i-वां राउंड सेक्टर rounds[i-1] से शुरू होता है और सेक्टर rounds[i] पर समाप्त होता है। उदाहरण के लिए, यदि राउंड 1 सेक्टर rounds[0] से शुरू होता है और सेक्टर rounds[1] पर समाप्त होता है। तो हमें आरोही क्रम में सॉर्ट किए गए सबसे अधिक विजिट किए गए सेक्टर ढूंढने हैं। (ट्रैक नंबर वामावर्त दिशा में सेक्टर नंबर के आरोही क्रम में हैं)

इसलिए, यदि इनपुट है: n = 4, rounds = [1,3,1,2], तो आउटपुट [1, 2] होगा।

क्योंकि दौड़ सेक्टर 1 से शुरू होती है। विजिट किए गए सेक्टर का क्रम इस प्रकार है: [1,2,3 (पहले राउंड का अंत),4,1 (दूसरे राउंड का अंत), 2 (तीसरे राउंड का अंत)]। यहां सेक्टर 1 और 2 दोनों दो बार विजिट किए गए हैं और वे सबसे अधिक विजिट किए गए सेक्टर हैं। और सेक्टर 3 और 4 केवल एक बार विजिट किए गए हैं।

हल करने के चरण

• d := एक नया मैप
• j को 1 से n तक के लिए: d[j] := 0
• d[rounds[0]] := 1
• i को 1 से rounds के आकार - 1 तक के लिए:
  • यदि rounds[i] > rounds[i-1]:
    • j को rounds[i-1]+1 से rounds[i]+1 तक के लिए: d[j]++
  • अन्यथा:
    • j को rounds[i-1]+1 से n तक के लिए: d[j]++
    • j को 1 से rounds[i] तक के लिए: d[j]++
• curr := d[rounds[0]]
• out := [rounds[0]]
• i को 1 से n तक के लिए:
  • यदि i != rounds[0]:
    • यदि d[i] > curr: curr := d[i], out := [i]
    • अन्यथा यदि d[i] == curr: out के साथ i जोड़ें
• सॉर्ट करने के बाद out वापस करें

उदाहरण (Python)

def solve(n, rounds):
    d = {}
    for j in range(1, n+1):
        d[j] = 0
    d[rounds[0]] = 1
    for i in range(1, len(rounds)):
        if rounds[i] > rounds[i-1]:
            for j in range(rounds[i-1]+1, rounds[i]+1):
                d[j] += 1
        else:
            for j in range(rounds[i-1]+1, n+1):
                d[j] += 1
            for j in range(1, rounds[i]+1):
                d[j] += 1
    curr = d[rounds[0]]
    out = [rounds[0]]
    for i in range(1, n+1):
        if i != rounds[0]:
            if d[i] > curr:
                curr = d[i]
                out = [i]
            elif d[i] == curr:
                out = out + [i]
    return sorted(out)

n = 4
rounds = [1, 3, 1, 2]
print(solve(n, rounds))

इनपुट

4, [1,3,1,2]

आउटपुट

[1, 2]