Saltar al contenido

Encuentre números enteros tales que A contenga exactamente X enteros distintos mayores que A{i]

Dada una matriz A[] De No enteros, la tarea es imprimir el número de enteros i de 1 a N, para los cuales A contiene exactamente X enteros distintos (para X = 0 a N-1) mayores que Ai

Ejemplos:

Entrada: n = 6, un[] = {2, 7, 1, 8, 2, 8}
Producción: {2, 1, 2, 1, 0, 0}
Explicación: Consideramos X = 2.
A[1] = 2: A contiene 2 enteros distintos mayores que 2 (7 y 8)
A[2] = 7: A contiene 1 entero distinto mayor que 7 (8)
A[3] = 1: A contiene 3 enteros distintos mayores que 1 (2, 7 y 8)
A[4] = 8: A no contiene enteros distintos mayores que 8
A[5] = 2: A contiene 2 enteros distintos mayores que 2 (7 y 8)
A[6] = 8: A no contiene enteros distintos mayores que 8
Así, la condición dada se cumple para i=1 y 5 en el caso de X=2.

Entrada: n = 1, un[] = {1}
Producción: 1

Acercarse: Para resolver el problema siga las siguientes observaciones:

Observaciones:

Si almacenamos la frecuencia de cada elemento del arreglo en un hashmap y lo ordenamos en orden descendente por claves, entonces:

Deje que el hashmap sea – ((u1F1), (tu2F2)….(tuNoFNo)) donde fI es la frecuencia del elemento uI y u1 > u2 > ……un.

  • Para cada i = 1 an, hay i – 1 enteros distintos mayores que uI. Así, para cualquier X=0 an-1 la respuesta para X sería fX+1.
  • La respuesta para X = na N – 1 sería 0.

Con base en la observación anterior, se puede utilizar el siguiente enfoque para resolver el problema:

  • Declare un mapa (digamos mp) y coloque los elementos de la matriz A en él.
  • Iterar el mapa desde el final e imprimir las frecuencias de los elementos.
  • Para los elementos restantes (es decir, Nn), imprima Nn ceros.

Aquí está el código basado en el enfoque anterior:

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
#define int long long

// Function to Print the number of
// integers i from 1 to N such that A
// contains exactly X distinct integers
// greater than A{i]
void Solve(int N, int A[])
{

    // Declaring the hashmap mp
    map<int, int> mp;

    // Inserting elements of A into mp
    for (int i = 0; i < N; i++) {
        mp[A[i]]++;
    }

    // Finding the size of map
    int n = (int)mp.size();

    // Printing the frequencies of
    // elements in map in reverse order
    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        cout << it->second << " ";
    }

    // Printing N-n zeroes
    for (int i = 1; i <= N - n; i++) {
        cout << 0 << " ";
    }
}

// Driver code
int32_t main()
{
    int N = 6;
    int A[] = { 2, 7, 1, 8, 2, 8 };

    // Function Call
    Solve(N, A);
    return 0;
}

Complejidad del tiempo: O(N*log(N))
Espacio Auxiliar: EN)