n개의 요소가 있는 정렬된 배열이 하나 있다고 가정합니다. 배열이 정렬됩니다. 더 작은 요소의 수가 더 큰 요소의 수와 동일한 배열에 요소가 존재하는지 여부를 찾아야 합니다. 배열에 등호점이 여러 번 나타나면 처음 나타나는 인덱스를 반환합니다. 그러한 점이 없으면 -1을 반환합니다. 요소가 A =[1, 1, 2, 3, 3, 3, 3, 3]과 같다고 가정하고 등점은 인덱스 2에 있고 요소는 A[2] =2입니다. 요소는 1이고 하나의 더 큰 요소는 3입니다.
모든 고유한 요소를 저장하기 위해 하나의 보조 배열을 만듭니다. 고유한 요소의 개수가 짝수이면 동일한 점을 찾을 수 없으며 그렇지 않으면 중간 요소가 중간점이 됩니다.
예시
#include<iostream>
using namespace std;
int searchEqualPoint(int arr[], int n) {
int aux_arr[n];
int i = 0, aux_index = 0;
while (i < n) {
aux_arr[aux_index++] = i++;
while (i<n && arr[i] == arr[i-1])
i++;
}
return (aux_index & 1)? aux_arr[aux_index>>1] : -1;
}
int main() {
int arr[] = {1, 1, 2, 3, 3, 3, 3, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int index = searchEqualPoint(arr, n);
if (index != -1)
cout << "Equal Point is: " << arr[index];
else
cout << "No Equal Point exists";
} 출력
Equal Point is: 2