Cho mảng đã sắp xếp. Tìm phần tử mà số lượng phần tử nhỏ hơn nó bằng số lượng phần tử lớn hơn nó. Nếu có nhiều, trả về chỉ số đầu tiên. Ví dụ: [1,1,2,3,3,3,3,3] → chỉ số 2 (giá trị 2), vì có 1 phần tử nhỏ hơn (1) và 1 phần tử lớn hơn (3).
Tạo mảng phụ lưu chỉ số của các phần tử riêng biệt. Nếu số phần tử riêng biệt là lẻ, phần tử giữa chính là điểm cân bằng, trả về chỉ số gốc của nó. Nếu chẵn, trả về -1.
Ví dụ
#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";
}
Kết quả
Equal Point is: 2