Giả sử chúng ta đã cho một mảng các số nguyên. Nhiệm vụ là tìm chỉ số của một phần tử cụ thể trong mảng đã cho. Ví dụ,
Đầu vào-1 -
N = 8
A[ ] = { 1,2,4,3,3,1,1,5} Đầu ra -
1
Giải thích - Trong mảng các số nguyên đã cho, số xuất hiện nhiều nhất là ‘1’. Do đó, đầu ra là "1".
Đầu vào-2 -
N = 6
A[ ] = {1,5,4,4,1,1} Đầu ra -
1
Giải thích - Trong mảng các số nguyên đã cho, số xuất hiện nhiều nhất là ‘1’. Do đó, chúng ta có thể trả về kết quả đầu ra là ‘1’.
Phương pháp tiếp cận để giải quyết vấn đề này
Mảng đã cho chứa nhiều số nguyên trong đó chúng ta phải tìm phần tử xuất hiện nhiều nhất trong mảng. Để giải quyết vấn đề này trong thời gian tuyến tính O (n) và Không gian tuyến tính O (n), chúng ta có thể sử dụng cách tiếp cận của một bản đồ băm.
Trong cách tiếp cận này, chúng tôi sẽ tạo một bản đồ không có thứ tự (Thư viện STL) bao gồm cặp khóa-giá trị trong đó khóa sẽ là một phần tử và Giá trị sẽ là sự xuất hiện của phần tử. Trong khi duyệt qua bản đồ, chúng tôi sẽ tìm thấy số lượng xuất hiện tối đa và trả về số đó dưới dạng Đầu ra.
-
Lấy đầu vào một mảng có kích thước N
-
Hàm số nguyên maxOcchood (int A [], int size) nhận một mảng và kích thước của nó làm đầu vào và trả về các số có tần suất tối đa.
-
Tạo một bản đồ băm của tất cả các phần tử của mảng bằng cách lấy khóa làm phần tử và giá trị làm tần số của nó.
-
Lặp lại bản đồ và kiểm tra xem có phần tử nào có tần suất xuất hiện nhiều nhất hay không rồi trả về kết quả là số. Ngược lại, nếu không có bất kỳ số nào trong mảng thì trả về ‘-1’.
Ví dụ
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");
}
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
Enter size of array: 6 Enter elements of array: 2 1 1 2 2 2 Majority Element is: 2