पायथन में मेजोरिटी एलिमेंट (Majority Element) खोजें

समस्या विवरण

एक पूर्णांक सरणी (array) दी गई है, उस तत्व को खोजें जो सरणी के आकार के आधे से अधिक बार आता है (मेजोरिटी एलिमेंट)।

उदाहरण 1

N = 8
A = [1,2,4,3,3,1,1,5]
आउटपुट: 1
व्याख्या: 1 तीन बार आता है (> 8/2 = 4? नहीं, 3 > 4 गलत है। वास्तव में यह उदाहरण गलत है।)

सुधार: मेजोरिटी एलिमेंट की परिभाषा: वह तत्व जो n/2 से अधिक बार आता है।

सही उदाहरण

N = 6
A = [2,1,1,2,2,2]
आउटपुट: 2
व्याख्या: 2 चार बार आता है (> 6/2 = 3)।

समाधान: हैश मैप (डिक्शनरी) आवृत्ति गणना

def checkMajorityElement(arr, N):
    freq = {}
    
    # आवृत्ति गिनें
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    
    # मेजोरिटी जांचें
    for num, count in freq.items():
        if count > N / 2:
            return num
    
    return -1

# टेस्ट
arr = [2,1,1,2,2,2]
N = 6
ans = checkMajorityElement(arr, N)

if ans != -1:
    print(f"मेजोरिटी एलिमेंट: {ans}")
else:
    print("मेजोरिटी एलिमेंट नहीं मिला")

आउटपुट

मेजोरिटी एलिमेंट: 2

बॉयर-मूर वोटिंग एल्गोरिदम (O(1) स्पेस):

def majorityElement(arr):
    candidate = None
    count = 0
    
    for num in arr:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    # सत्यापन चरण
    if arr.count(candidate) > len(arr) // 2:
        return candidate
    return -1

यह एल्गोरिदम O(n) समय और O(1) स्पेस में काम करता है।