查找数组中每个元素的超出者计数-yiteyi-C++库

数组中某个元素的超出者是其右边较大的元素，因此如果i 例如：

null

Input:  [2, 7, 5, 3, 0, 8, 1]Output: [4, 1, 1, 1, 2, 0, 0]

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

方法1（天真） 简单的解决方案是运行两个循环。对于数组中的每一个元素，我们都会计算其右边大于它的所有元素。这个解决方案的复杂性是O（n） ^2. )

C++

                         // Naive C++ program to find surpasser count of                       
                         // each element in array                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find surpasser count of each element                       
                         // in array                       
                         void                                     findSurpasser(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // stores surpasser count for element arr[i]                       
                                                 int                                     count = 0;                       
                                                 for                                     (                                     int                                     j = i + 1; j < n; j++)                       
                                                 if                                     (arr[j] > arr[i])                       
                                                 count++;                       
           
                                                 cout << count <<                                     " "                                     ;                       
                                                 }                       
                         }                       
           
                         /* Function to print an array */                       
                         void                                     printArray(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 printf                                     (                                     "%d "                                     , arr[i]);                       
                                                 printf                                     (                                     ""                                     );                       
                         }                       
           
                         /* Driver program to test above functions */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 2, 7, 5, 3, 0, 8, 1 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 printf                                     (                                     "Given array is "                                     );                       
                                                 printArray(arr, n);                       
           
                                                 printf                                     (                                     "Surpasser Count of array is "                                     );                       
                                                 findSurpasser(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Naive Java program to find surpasser count                       
                         // of each element in array                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                                                 // Function to find surpasser count of                       
                                                 // each element in array                       
                                                 static                                     void                                     findSurpasser(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                   
                                                 // stores surpasser count for                       
                                                 // element arr[i]                       
                                                 int                                     count =                                     0                                     ;                       
                                                 for                                     (                                     int                                     j = i +                                     1                                     ; j < n; j++)                       
                                                 if                                     (arr[j] > arr[i])                       
                                                 count++;                       
                                   
                                                 System.out.print(count +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 /* Function to print an array */                       
                                                 static                                     void                                     printArray(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 System.out.print( arr[i] +                                     " "                                     );                       
                                   
                                                 System.out.println();                       
                                                 }                       
                                   
                                                 // Driver program to test above functions                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     2                                     ,                                     7                                     ,                                     5                                     ,                                     3                                     ,                                     0                                     ,                                     8                                     ,                                     1                                     };                       
                                                 int                                     n = arr.length;                       
                                   
                                                 System.out.println(                                     "Given array is "                                     );                       
                                                 printArray(arr, n);                       
                                   
                                                 System.out.println(                                     "Surpasser Count of"                       
                                                 +                                     " array is "                                     );                       
                                                 findSurpasser(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anuj_67.                       

Python3

                         # Naive Python3 program to find                       
                         # surpasser count of each element in array                       
           
                         # Function to find surpasser count of                       
                         # each element in array                       
                         def                                     findSurpasser(arr, n):                       
           
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                   
                                                 # stores surpasser count for element                       
                                                 # arr[i]                       
                                                 count                                     =                                     0                                     ;                       
           
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n):                       
                                                 if                                     (arr[j] > arr[i]):                       
                                                 count                                     +                                     =                                     1                       
           
                                                 print                                     (count, end                                     =                                     " "                                     )                       
           
           
                         # Function to print an array                       
                         def                                     printArray(arr, n):                       
           
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                                 print                                     (arr[i], end                                     =                                     " "                                     )                       
                                   
                         # Driver program to test above functions                       
                         arr                                     =                                     [                                     2                                     ,                                     7                                     ,                                     5                                     ,                                     3                                     ,                                     0                                     ,                                     8                                     ,                                     1                                     ]                       
                         n                                     =                                     len                                     (arr)                       
           
                         print                                     (                                     "Given array is"                                     )                       
                         printArray(arr , n)                       
           
                         print                                     (                                     "Surpasser Count of array is"                                     );                       
                         findSurpasser(arr , n)                       
           
                         # This code is contributed by Smitha Dinesh Semwal                       

C#

                         // Naive C# program to find surpasser count                       
                         // of each element in array                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Function to find surpasser count of                       
                                                 // each element in array                       
                                                 static                                     void                                     findSurpasser(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // stores surpasser count for                       
                                                 // element arr[i]                       
                                                 int                                     count = 0;                       
                                                 for                                     (                                     int                                     j = i + 1; j < n; j++)                       
                                                 if                                     (arr[j] > arr[i])                       
                                                 count++;                       
                                   
                                                 Console.Write(count +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 /* Function to print an array */                       
                                                 static                                     void                                     printArray(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write( arr[i] +                                     " "                                     );                       
                                   
                                                 Console.WriteLine();                       
                                                 }                       
                                   
                                                 // Driver program to test above functions                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []arr = { 2, 7, 5, 3, 0, 8, 1 };                       
                                                 int                                     n = arr.Length;                       
                                   
                                                 Console.WriteLine(                                     "Given array is "                                     );                       
                                                 printArray(arr, n);                       
                                   
                                                 Console.WriteLine(                                     "Surpasser Count of"                       
                                                 +                                     " array is "                                     );                       
                                                 findSurpasser(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anuj_67.                       

PHP

                         <?php                       
                         // Naive PHP program to find                       
                         // surpasser count of each                       
                         // element in array                       
           
                         // Function to find surpasser                       
                         // count of each element in array                       
                         function                                     findSurpasser(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // stores surpasser count                       
                                                 // for element arr[i]                       
                                                 $count                                     = 0;                       
                                                 for                                     (                                     $j                                     =                                     $i                                     + 1;                                     $j                                     <                                     $n                                     ;                                     $j                                     ++)                       
                                                 if                                     (                                     $arr                                     [                                     $j                                     ] >                                     $arr                                     [                                     $i                                     ])                       
                                                 $count                                     ++;                       
           
                                                 echo                                     $count                                     ,                                     " "                                     ;                       
                                                 }                       
                         }                       
           
                         /* Function to print an array */                       
                         function                                     printArray(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 echo                                     $arr                                     [                                     $i                                     ],                                     " "                                     ;                       
                                                 echo                                     ""                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     ( 2, 7, 5, 3, 0, 8, 1 );                       
                         $n                                     =                                     count                                     (                                     $arr                                     );                       
           
                         echo                                     "Given array is "                                     ;                       
                         printArray(                                     $arr                                     ,                                     $n                                     );                       
           
                         echo                                     "Surpasser Count of array is "                                     ;                       
                         findSurpasser(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by Anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Naive Javascript program to find surpasser count                       
                         // of each element in array                       
           
                                                 // Function to find surpasser count of                       
                                                 // each element in array                       
                                                 function                                     findSurpasser(arr, n)                       
                                                 {                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // stores surpasser count for                       
                                                 // element arr[i]                       
                                                 let count = 0;                       
                                                 for                                     (let j = i + 1; j < n; j++)                       
                                                 if                                     (arr[j] > arr[i])                       
                                                 count++;                       
                                   
                                                 document.write(count +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 /* Function to print an array */                       
                                                 function                                     printArray(arr, n)                       
                                                 {                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write( arr[i] +                                     " "                                     );                       
                                   
                                                 document.write();                       
                                                 }                       
                                   
           
                         // Driver Code                       
                                   
                                                 let arr = [ 2, 7, 5, 3, 0, 8, 1 ];                       
                                                 let n = arr.length;                       
                                   
                                                 document.write(                                     "Given array is "                                     +                                     "<br />"                                     );                       
                                                 printArray(arr, n);                       
                                   
                                                 document.write(                                     "<br />"                                     );                       
                                   
                                                 document.write(                                     "Surpasser Count of"                       
                                                 +                                     " array is "                                     +                                     "<br />"                                     );                       
                                                 findSurpasser(arr, n);                       
                                   
                         </script>                       

输出：

Given array is 2 7 5 3 0 8 1 Surpasser Count of array is 4 1 1 1 2 0 0

时间复杂性： O（n） ^2. ) 方法2（使用合并排序） 对于数组中的任何元素，如果我们知道其右边小于该元素的元素数，就可以很容易地找出右边大于该元素的元素数。其思想是使用合并排序来计算数组中每个元素的反转数。因此，在位置i处元素的溢出计数将等于该位置处的“n–i–反转计数”，其中n是数组的大小。我们已经讨论过如何找到完整数组的反转计数在这里 .我们修改了所讨论的方法，以查找数组中每个元素的反转数，而不是返回整个数组的反转计数。此外，由于数组的所有元素都是不同的，我们维护了一个映射，该映射存储了数组中每个元素的反转计数。以下是C++实现上述思想的方法——

C++

                         // C++ program to find surpasser count of each element                       
                         // in array                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         /* Function to merge the two haves arr[l..m] and                       
                                                 arr[m+1..r] of array arr[] */                       
                         int                                     merge(                                     int                                     arr[],                                     int                                     l,                                     int                                     m,                                     int                                     r,                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > &hm)                       
                         {                       
                                                 int                                     i, j, k;                       
                                                 int                                     n1 = m - l + 1;                       
                                                 int                                     n2 = r - m;                       
           
                                                 /* create temp arrays */                       
                                                 int                                     L[n1], R[n2];                       
           
                                                 /* Copy data to temp arrays L[] and R[] */                       
                                                 for                                     (i = 0; i < n1; i++)                       
                                                 L[i] = arr[l + i];                       
           
                                                 for                                     (j = 0; j < n2; j++)                       
                                                 R[j] = arr[m + 1 + j];                       
           
                                                 /* Merge the temp arrays back into arr[l..r]*/                       
                                                 i = 0, j = 0, k = l;                       
                                                 int                                     c = 0;                       
                                                 while                                     (i < n1 && j < n2)                       
                                                 {                       
                                                 if                                     (L[i] <= R[j])                       
                                                 {                       
                                                 // increment inversion count of L[i]                       
                                                 hm[L[i]] += c;                       
                                                 arr[k++] = L[i++];                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 arr[k++] = R[j++];                       
           
                                                 // inversion found                       
                                                 c++;                       
                                                 }                       
                                                 }                       
           
                                                 /* Copy the remaining elements of L[], if                       
                                                 there are any */                       
                                                 while                                     (i < n1)                       
                                                 {                       
                                                 hm[L[i]] += c;                       
                                                 arr[k++] = L[i++];                       
                                                 }                       
           
                                                 /* Copy the remaining elements of R[], if                       
                                                 there are any */                       
                                                 while                                     (j < n2)                       
                                                 arr[k++] = R[j++];                       
                         }                       
           
                         /* l is for left index and r is right index of                       
                         the sub-array of arr to be sorted */                       
                         int                                     mergeSort(                                     int                                     arr[],                                     int                                     l,                                     int                                     r,                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > &hm)                       
                         {                       
                                                 if                                     (l < r)                       
                                                 {                       
                                                 int                                     m = l + (r - l) / 2;                       
                                                 mergeSort(arr, l, m, hm);                       
                                                 mergeSort(arr, m + 1, r, hm);                       
                                                 merge(arr, l, m, r, hm);                       
                                                 }                       
                         }                       
           
                         /* Function to print an array */                       
                         void                                     printArray(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 printf                                     (                                     "%d "                                     , arr[i]);                       
                                                 printf                                     (                                     ""                                     );                       
                         }                       
           
                         void                                     findSurpasser(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // To store inversion count for elements                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > hm;                       
           
                                                 // To store copy of array                       
                                                 int                                     dup[n];                       
                                                 memcpy                                     (dup, arr, n*                                     sizeof                                     (arr[0]));                       
           
                                                 // Sort the copy and store inversion count                       
                                                 // for each element.                       
                                                 mergeSort(dup, 0, n - 1, hm);                       
           
                                                 printf                                     (                                     "Surpasser Count of array is "                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 printf                                     (                                     "%d "                                     , (n - 1) - i - hm[arr[i]]);                       
                         }                       
           
                         /* Driver program to test above functions */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 2, 7, 5, 3, 0, 8, 1 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 printf                                     (                                     "Given array is "                                     );                       
                                                 printArray(arr, n);                       
           
                                                 findSurpasser(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

输出：

Given array is 2 7 5 3 0 8 1 Surpasser Count of array is 4 1 1 1 2 0 0

上述解的时间复杂度为O（nlogn）。本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章