องค์ประกอบส่วนใหญ่ใน Java

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

อินพุต-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'

ตัวอย่าง

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
class Majority_Element{
   public static int checkMajorityElement(int arr[], int N){
      Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
      for (int i = 0; i < N; i++){
         if (mp.containsKey(arr[i]))
            mp.put(arr[i], mp.get(arr[i]) + 1);
         else
            mp.put(arr[i], 1);
      }
      for (Map.Entry<Integer, Integer> entry : mp.entrySet()){
         if (entry.getValue() > (N / 2))
            return entry.getKey();
      }
      return -1;
   }
   public static void main(String args[]){
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter size of array:");
      int N = 6;
      int arr[] = {2,1,1,2,2,2};
      System.out.println("Enter elements of array:");
      for (int i = 0; i < N; i++)
         arr[i] = sc.nextInt();
      int ans = checkMajorityElement(arr, N);
      if (ans != -1)
         System.out.println("Majority Element is: " + ans);
      else
         System.out.println("No majority element in array");
   }
}

ผลลัพธ์

การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น

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