정수 배열이 있다고 가정해 보겠습니다. 작업은 주어진 배열에서 특정 요소의 인덱스를 찾는 것입니다. 예를 들어,
입력-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'을 반환합니다.
예
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