在C ++中具有重复项的排序数组中查找等于（或中间）点

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个包含n个元素的排序数组。数组已排序。我们必须找到一个元素是否存在于数组中，其中较小元素的数量与较大元素的数量相同。如果相等点在数组中出现多次，则返回第一次出现的索引。如果不存在这样的点，则返回-1。假设元素像A = [1、2、1、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

以上是 在C ++中具有重复项的排序数组中查找等于（或中间）点 的全部内容， 来源链接： utcz.com/z/338105.html