Un superador de un elemento de un arreglo es un elemento mayor a su derecha, por lo tanto x[j] es un superador de x[i] si i < j y x[i] < x[j]. El recuento de superadores de un elemento es el número de superadores. Dada una array de enteros distintos, para cada elemento de la array encuentre su cuenta superior, es decir, cuente la cantidad de elementos a la derecha que son mayores que ese elemento.
Ejemplos:
Input: [2, 7, 5, 3, 0, 8, 1] Output: [4, 1, 1, 1, 2, 0, 0]
Método 1 (ingenuo) : la solución ingenua sería ejecutar dos bucles. Para cada elemento de la array, contamos todos los elementos mayores que él a su derecha. La complejidad de esta solución es O(n 2 )
Implementación:
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("\n");
}
/* 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 \n");
printArray(arr, n);
printf("Surpasser Count of array is \n");
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("\nSurpasser 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 "\n";
}
// Driver Code
$arr = array( 2, 7, 5, 3, 0, 8, 1 );
$n = count($arr);
echo "Given array is \n";
printArray($arr, $n);
echo "Surpasser Count of array is \n";
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
Complejidad del tiempo : O(n 2 )
Método 2 (Usa Merge Sort): para cualquier elemento de la array, podemos encontrar fácilmente la cantidad de elementos a la derecha que son mayores que ese elemento si conocemos la cantidad de elementos a su derecha que son menores que ese elemento. La idea es contar el número de inversiones para cada elemento de la array utilizando la ordenación por combinación. Entonces, el conteo de superadores de un elemento en la posición i será igual a “n – i – inversion-count” en esa posición donde n es el tamaño de la array.
Ya hemos discutido cómo encontrar el recuento de inversión de una array completa aquí . Hemos modificado el enfoque discutido para encontrar el número de inversiones para cada elemento de la array en lugar de devolver el recuento de inversiones de toda la array. Además, como todos los elementos de la array son distintos, mantenemos un mapa que almacena el recuento de inversiones para cada elemento de la array.
A continuación se muestra la implementación en C++ de la idea anterior
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("\n");
}
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 \n");
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 \n");
printArray(arr, n);
findSurpasser(arr, n);
return 0;
}
Python3
# Python program to find surpasser count of each element
# in array
# Function to merge the two haves arr[l..m] and
# arr[m+1..r] of array arr[]
def merge(arr, l, m, r, hm):
n1 = m - l + 1
n2 = r - m
# create temp arrays
L= [0 for i in range(n1)]
R = [0 for i in range(n2)]
# Copy data to temp arrays L[] and R[]
for i in range(n1):
L[i] = arr[l + i]
for j in range(n2):
R[j] = arr[m + 1 + j]
# Merge the temp arrays back into arr[l..r]
i,j,k,c = 0,0,l,0
while (i < n1 and j < n2):
if (L[i] <= R[j]):
# increment inversion count of L[i]
if(L[i] in hm):
hm[L[i]] += c
else :
hm[L[i]] = c
arr[k] = L[i]
k += 1
i += 1
else:
arr[k] = R[j]
# inversion found
c += 1
k += 1
j += 1
# Copy the remaining elements of L[], if
# there are any
while (i < n1):
if(L[i] in hm):
hm[L[i]] += c
else :
hm[L[i]] = c
arr[k] = L[i]
k += 1
i += 1
# Copy the remaining elements of R[], if
# there are any
while (j < n2):
arr[k] = R[j]
k += 1
j += 1
# l is for left index and r is right index of
# the sub-array of arr to be sorted
def mergeSort(arr,l,r,hm):
if (l < r):
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
def printArray(arr,n):
for i in range(n):
print(arr[i],end = " ")
print("")
def findSurpasser(arr, n):
# To store inversion count for elements
hm = {}
# To store copy of array
dup = arr[:]
# Sort the copy and store inversion count
# for each element.
mergeSort(dup, 0, n - 1, hm)
print("Surpasser Count of array is ")
for i in range(n):
print((n - 1) - i - (hm[arr[i]] if arr[i] in hm else 0),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)
findSurpasser(arr, n)
# This code is contributed by shinjanpatra
Given array is 2 7 5 3 0 8 1 Surpasser Count of array is 4 1 1 1 2 0 0
La complejidad temporal de la solución anterior es O(nlogn).
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA