在具有重复项的排序数组中找到相等（或中间）点-yiteyi-C++库

给定一个n大小的排序数组，任务是找出数组中是否存在一个元素，其中较小元素的数量等于较大元素的数量。如果Equal Point在输入数组中多次出现，则返回其第一次出现的索引。如果不存在，则返回-1。 例如：

null

Input  : arr[] = {1, 2, 3, 3, 3, 3}Output : 1Equal Point is arr[1] which is 2. Number ofelements smaller than 2 and greater than 2 are same.Input  : arr[] = {1, 2, 3, 3, 3, 3, 4, 4}Output : Equal Point does not exist.Input : arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 6, 7}Output : 3First occurrence of equal point is arr[3]

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 缺乏经验的 方法是取每个元素，计算有多少元素比那个元素小，然后是更大的元素。然后比较两者是否相等。一 有效率的 方法是创建一个辅助数组，并在其中存储所有不同的元素。如果不同元素的计数为偶数，则不存在等分。如果count为奇数，则等分点为辅助数组的中点。下面是上述想法的实现。

C++

                         // C++ program to find Equal point in a sorted array                       
                         // which may have many duplicates.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns value of Equal point in a sorted array arr[]                       
                         // It returns -1 if there is no Equal Point.                       
                         int                                     findEqualPoint(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // To store first indexes of distinct elements of arr[]                       
                                                 int                                     distArr[n];                       
           
                                                 // Traverse input array and store indexes of first                       
                                                 // occurrences of distinct elements in distArr[]                       
                                                 int                                     i = 0, di = 0;                       
                                                 while                                     (i < n)                       
                                                 {                       
                                                 // This element must be first occurrence of a                       
                                                 // number (this is made sure by below loop),                       
                                                 // so add it to distinct array.                       
                                                 distArr[di++] = i++;                       
           
                                                 // Avoid all copies of arr[i] and move to next                       
                                                 // distinct element.                       
                                                 while                                     (i<n && arr[i] == arr[i-1])                       
                                                 i++;                       
                                                 }                       
           
                                                 // di now has total number of distinct elements.                       
                                                 // If di is odd, then equal point exists and is at                       
                                                 // di/2, otherwise return -1.                       
                                                 return                                     (di & 1)? distArr[di>>1] : -1;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 6, 7};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 int                                     index = findEqualPoint(arr, n);                       
                                                 if                                     (index != -1)                       
                                                 cout <<                                     "Equal Point = "                                     << arr[index] ;                       
                                                 else                       
                                                 cout <<                                     "Equal Point does not exists"                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         //Java program to find Equal point in a sorted array                       
                         // which may have many duplicates.                       
           
                         class                                     Test                       
                         {                       
                                                 // Returns value of Equal point in a sorted array arr[]                       
                                                 // It returns -1 if there is no Equal Point.                       
                                                 static                                     int                                     findEqualPoint(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 // To store first indexes of distinct elements of arr[]                       
                                                 int                                     distArr[] =                                     new                                     int                                     [n];                       
                                   
                                                 // Traverse input array and store indexes of first                       
                                                 // occurrences of distinct elements in distArr[]                       
                                                 int                                     i =                                     0                                     , di =                                     0                                     ;                       
                                                 while                                     (i < n)                       
                                                 {                       
                                                 // This element must be first occurrence of a                       
                                                 // number (this is made sure by below loop),                       
                                                 // so add it to distinct array.                       
                                                 distArr[di++] = i++;                       
                                   
                                                 // Avoid all copies of arr[i] and move to next                       
                                                 // distinct element.                       
                                                 while                                     (i<n && arr[i] == arr[i-                                     1                                     ])                       
                                                 i++;                       
                                                 }                       
                                   
                                                 // di now has total number of distinct elements.                       
                                                 // If di is odd, then equal point exists and is at                       
                                                 // di/2, otherwise return -1.                       
                                                 return                                     (di &                                     1                                     )!=                                     0                                     ? distArr[di>>                                     1                                     ] : -                                     1                                     ;                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     6                                     ,                                     6                                     ,                                     7                                     };                       
                                   
                                                 int                                     index = findEqualPoint(arr, arr.length);                       
                                                 System.out.println(index != -                                     1                                     ?                                     "Equal Point = "                                     + arr[index]                       
                                                 :                                     "Equal Point does not exists"                                     );                       
                                                 }                       
                         }                       

Python 3

                         # Python 3 program to find                       
                         # Equal point in a sorted                       
                         # array which may have                       
                         # many duplicates.                       
           
                         # Returns value of Equal                       
                         # point in a sorted array                       
                         # arr[]. It returns -1 if                       
                         # there is no Equal Point.                       
                         def                                     findEqualPoint(arr, n):                       
           
                                                 # To store first indexes of                       
                                                 # distinct elements of arr[]                       
                                                 distArr                                     =                                     [                                     0                                     ]                                     *                                     n                       
           
                                                 # Traverse input array and                       
                                                 # store indexes of first                       
                                                 # occurrences of distinct                       
                                                 # elements in distArr[]                       
                                                 i                                     =                                     0                       
                                                 di                                     =                                     0                       
                                                 while                                     (i < n):                       
                                   
                                                 # This element must be                       
                                                 # first occurrence of a                       
                                                 # number (this is made                       
                                                 # sure by below loop),                       
                                                 # so add it to distinct array.                       
                                                 distArr[di]                                     =                                     i                       
                                                 di                                     +                                     =                                     1                       
                                                 i                                     +                                     =                                     1                       
           
                                                 # Avoid all copies of                       
                                                 # arr[i] and move to                       
                                                 # next distinct element.                       
                                                 while                                     (i < n                                     and                       
                                                 arr[i]                                     =                                     =                                     arr[i                                     -                                     1                                     ]):                       
                                                 i                                     +                                     =                                     1                       
                                   
                                                 # di now has total number                       
                                                 # of distinct elements.                       
                                                 # If di is odd, then equal                       
                                                 # point exists and is at                       
                                                 # di/2, otherwise return -1.                       
                                                 return                                     distArr[di >>                                     1                                     ]                                     if                                     (di &                                     1                                     )                                     else                                     -                                     1                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     4                                     ,                       
                                                 5                                     ,                                     6                                     ,                                     6                                     ,                                     6                                     ,                                     7                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         index                                     =                                     findEqualPoint(arr, n)                       
                         if                                     (index !                                     =                                     -                                     1                                     ):                       
                                                 print                                     (                                     "Equal Point = "                                     ,                       
                                                 arr[index])                       
                         else                                     :                       
                                                 print                                     (                                     "Equal Point does "                                     +                       
                                                 "not exists"                                     )                       
           
                         # This code is contributed                       
                         # by Smitha                       

C#

                         // C# program to find Equal                       
                         // point in a sorted array                       
                         // which may have many duplicates.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Returns value of Equal point                       
                                                 // in a sorted array arr[]                       
                                                 // It returns -1 if there                       
                                                 // is no Equal Point.                       
                                                 static                                     int                                     findEqualPoint(                                     int                                     []arr,                       
                                                 int                                     n)                       
                                                 {                       
                                                 // To store first indexes of                       
                                                 // distinct elements of arr[]                       
                                                 int                                     []distArr =                                     new                                     int                                     [n];                       
                                   
                                                 // Traverse input array and                       
                                                 // store indexes of first                       
                                                 // occurrences of distinct                       
                                                 // elements in distArr[]                       
                                                 int                                     i = 0, di = 0;                       
                                                 while                                     (i < n)                       
                                                 {                       
                                                 // This element must be                       
                                                 // first occurrence of a                       
                                                 // number (this is made                       
                                                 // sure by below loop),                       
                                                 // so add it to distinct array.                       
                                                 distArr[di++] = i++;                       
                                   
                                                 // Avoid all copies of                       
                                                 // arr[i] and move to                       
                                                 // next distinct element.                       
                                                 while                                     (i < n && arr[i] == arr[i - 1])                       
                                                 i++;                       
                                                 }                       
                                   
                                                 // di now has total number                       
                                                 // of distinct elements.                       
                                                 // If di is odd, then equal                       
                                                 // point exists and is at                       
                                                 // di/2, otherwise return -1.                       
                                                 return                                     (di & 1) != 0 ?                       
                                                 distArr[di >> 1] :                       
                                                 -1;                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = {1, 2, 3, 4, 4,                       
                                                 5, 6, 6, 6, 7};                       
                                   
                                                 int                                     index = findEqualPoint(arr, arr.Length);                       
                                                 Console.Write(index != -1 ?                       
                                                 "Equal Point = "                                     + arr[index] :                       
                                                 "Equal Point does not exists"                                     );                       
                                                 }                       
                         }                       

PHP

                         <?php                       
                         // PHP program to find Equal point in a                       
                         // sorted array which may have many                       
                         // duplicates.                       
           
                         // Returns value of Equal point in a                       
                         // sorted array arr[] It returns -1                       
                         // if there is no Equal Point.                       
                         function                                     findEqualPoint(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 // To store first indexes of distinct                       
                                                 // elements of arr[]                       
                                                 $distArr                                     =                                     array                                     ();                       
           
                                                 // Traverse input array and store                       
                                                 // indexes of first occurrences of                       
                                                 // distinct elements in distArr[]                       
                                                 $i                                     = 0;                                     $di                                     = 0;                       
                                   
                                                 while                                     (                                     $i                                     <                                     $n                                     )                       
                                                 {                       
                                                 // This element must be first                       
                                                 // occurrence of a number (this                       
                                                 // is made sure by below loop),                       
                                                 // so add it to distinct array.                       
                                                 $distArr                                     [                                     $di                                     ++] =                                     $i                                     ++;                       
           
                                                 // Avoid all copies of arr[i]                       
                                                 // and move to next distinct                       
                                                 // element.                       
                                                 while                                     (                                     $i                                     <                                     $n                                     and                       
                                                 $arr                                     [                                     $i                                     ] ==                                     $arr                                     [                                     $i                                     -1])                       
                                                 $i                                     ++;                       
                                                 }                       
           
                                                 // di now has total number of                       
                                                 // distinct elements. If di is odd,                       
                                                 // then equal point exists and is                       
                                                 // at di/2, otherwise return -1.                       
                                                 return                                     (                                     $di                                     & 1)?                                     $distArr                                     [                                     $di                                     >>1] : -1;                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (1, 2, 3, 4, 4, 5, 6, 6, 6, 7);                       
                         $n                                     =                                     count                                     (                                     $arr                                     );                       
                         $index                                     = findEqualPoint(                                     $arr                                     ,                                     $n                                     );                       
                         if                                     (                                     $index                                     != -1)                       
                                                 echo                                     "Equal Point = "                                     ,                                     $arr                                     [                                     $index                                     ] ;                       
                         else                       
                                                 echo                                     "Equal Point does not exists"                                     ;                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // JavaScript program to find Equal                       
                                                 // point in a sorted array                       
                                                 // which may have many duplicates.                       
                                   
                                                 // Returns value of Equal point                       
                                                 // in a sorted array arr[]                       
                                                 // It returns -1 if there                       
                                                 // is no Equal Point.                       
                                                 function                                     findEqualPoint(arr, n)                       
                                                 {                       
                                                 // To store first indexes of                       
                                                 // distinct elements of arr[]                       
                                                 let distArr =                                     new                                     Array(n);                       
                                                 distArr.fill(0);                       
                                   
                                                 // Traverse input array and                       
                                                 // store indexes of first                       
                                                 // occurrences of distinct                       
                                                 // elements in distArr[]                       
                                                 let i = 0, di = 0;                       
                                                 while                                     (i < n)                       
                                                 {                       
                                                 // This element must be                       
                                                 // first occurrence of a                       
                                                 // number (this is made                       
                                                 // sure by below loop),                       
                                                 // so add it to distinct array.                       
                                                 distArr[di++] = i++;                       
                                   
                                                 // Avoid all copies of                       
                                                 // arr[i] and move to                       
                                                 // next distinct element.                       
                                                 while                                     (i < n && arr[i] == arr[i - 1])                       
                                                 i++;                       
                                                 }                       
                                   
                                                 // di now has total number                       
                                                 // of distinct elements.                       
                                                 // If di is odd, then equal                       
                                                 // point exists and is at                       
                                                 // di/2, otherwise return -1.                       
                                                 return                                     (di & 1) != 0 ?                       
                                                 distArr[di >> 1] :                       
                                                 -1;                       
                                                 }                       
                                   
                                                 let arr = [1, 2, 3, 4, 4, 5, 6, 6, 6, 7];                       
                                   
                                                 let index = findEqualPoint(arr, arr.length);                       
                                                 document.write(index != -1 ?                       
                                                 "Equal Point = "                                     + arr[index] :                       
                                                 "Equal Point does not exists"                                     );                       
                                   
                         </script>                       

输出：

Equal Point = 4

时间复杂性： O（n） 辅助空间： O（n） 空间优化： 我们可以通过遍历数组两次而不是一次来减少额外的空间。

通过遍历输入数组来计算不同元素的总数。让这个数算了吧。
如果distCount为偶数，则返回-1。
如果distCount为奇数，则再次遍历数组，并在distCount/2处停止并返回此索引。

感谢Pavan Kumar J S提出这种空间优化方法。本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章