정수 배열을 제공했다고 가정해 보겠습니다. 작업은 주어진 배열에서 특정 요소의 인덱스를 찾는 것입니다. 예를 들어,
입력-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)에서 이 문제를 해결하기 위해 해시맵 접근 방식을 사용할 수 있습니다.
이 접근 방식에서 우리는 키가 요소가 되고 값이 요소의 발생이 되는 키-값 쌍으로 구성된 정렬되지 않은 맵(STL 라이브러리)을 만들 것입니다. 지도를 탐색하는 동안 숫자의 최대 발생을 찾고 숫자를 출력으로 반환합니다.
-
N
크기의 배열을 입력하십시오. -
정수 함수 maxOccurrence(int A[], int size)는 배열과 그 크기를 입력으로 받아 최대 빈도의 숫자를 반환합니다.
-
키를 요소로, 값을 빈도로 사용하여 배열의 모든 요소에 대한 해시맵을 생성합니다.
-
맵을 반복하고 가장 빈도가 높은 요소가 있는지 확인한 다음 결과를 숫자로 반환합니다. 그렇지 않고 배열에 숫자가 없으면 '-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