องค์ประกอบส่วนใหญ่ใน 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) เราสามารถใช้แนวทางของแฮชแมปได้

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

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

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

• การสร้าง hashmap ขององค์ประกอบทั้งหมดของอาร์เรย์โดยใช้คีย์เป็นองค์ประกอบและค่าเป็นความถี่

• วนซ้ำบนแผนที่และตรวจสอบว่าองค์ประกอบใดที่มีความถี่มากที่สุดแล้วส่งคืนผลลัพธ์เป็นตัวเลข มิฉะนั้น ถ้าไม่มีตัวเลขอยู่ในอาร์เรย์ ให้คืนค่า '-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