Majority Element ใน Python

สมมติเรามีอาร์เรย์ของจำนวนเต็ม งานคือหาดัชนีของสมาชิกเฉพาะในอาร์เรย์ที่กำหนด ตัวอย่างเช่น

อินพุต-1 -

N = 8 A[ ] = { 1,2,4,3,3,1,1,5}

เอาต์พุต -

1

คำอธิบาย - ในอาร์เรย์ที่กำหนด ตัวเลขที่ปรากฏมากที่สุดคือ '1' ดังนั้นเอาต์พุตคือ '1'

อินพุต-2 -

N = 6 A[ ] = {1,5,4,4,1,1}

เอาต์พุต -

1

คำอธิบาย - ในอาร์เรย์ที่กำหนด ตัวเลขที่ปรากฏมากที่สุดคือ '1' ดังนั้นเราสามารถคืนค่า '1' ได้

แนวทางแก้ปัญหา

อาร์เรย์ที่กำหนดมีหลายจำนวนเต็ม ซึ่งเราต้องหาสมาชิกที่พบบ่อยที่สุดในอาร์เรย์ เพื่อแก้ปัญหานี้ในเวลา O(n) และพื้นที่ O(n) เราสามารถใช้แนวทางแฮชแมป (hashmap)

ในแนวทางนี้ เราจะสร้างแฮชแมป (unordered map จาก STL Library) ที่ประกอบด้วยคู่ key-value โดย key จะเป็นสมาชิก และ Value จะเป็นจำนวนครั้งที่เกิดขึ้น ขณะวนลูปผ่านแมป เราจะหาจำนวนครั้งที่มากที่สุดของตัวเลขและคืนค่าตัวเลขนั้นเป็นเอาต์พุต

• รับอินพุตอาร์เรย์ขนาด N

• ฟังก์ชัน Integer maxOccurrence(int A[], int size) รับอาร์เรย์และขนาด แล้วคืนค่าตัวเลขที่มีความถี่มากที่สุด

• สร้างแฮชแมปของทุกสมาชิกในอาร์เรย์ โดย key เป็นสมาชิก และ value เป็นความถี่

• วนลูปผ่านแมป และตรวจสอบว่ามีสมาชิกใดที่มีความถี่มากที่สุด คืนค่าตัวเลขนั้น มิฉะนั้นถ้าไม่มีตัวเลขในอาร์เรย์ คืนค่า '-1'

ตัวอย่าง

def checkMajorityElement(arr, N):
    mp = {}
    for i in range(0, N):
        if arr[i] in mp.keys():
            mp[arr[i]] += 1
        else:
            mp[arr[i]] = 1
    for key in mp:
        if mp[key] > (N / 2):
            return key
    return -1

print("Enter size of array:")
N = int(6)
print("Enter elements of array:")
arr = [2,1,1,2,2,2]
ans = checkMajorityElement(arr, N)
if ans != -1:
    print("Majority Element is: %d" % ans)
else:
    print("No majority element in array")

ผลลัพธ์

การรันโค้ดจะได้ผลลัพธ์ดังนี้

Enter size of array: 6 Enter elements of array: 2 1 1 2 2 2 Majority Element is: 2