Programa C++ para contar los elementos de la array más que todos los elementos a su izquierda y al menos K elementos a su derecha

Dada una array A[ ] que consta de N enteros distintos, la tarea es encontrar el número de elementos que son estrictamente mayores que todos los elementos que lo preceden y estrictamente mayores que al menos K elementos a su derecha.

Ejemplos:  

Entrada: A[] = {2, 5, 1, 7, 3, 4, 0}, K = 3 
Salida:
Explicación: 
Los únicos elementos de array que cumplen las condiciones dadas son: 

  • 5 : Mayor que todos los elementos a su izquierda {2} y al menos K(= 3) elementos a su derecha {1, 3, 4, 0}
  • 7 : Mayor que todos los elementos a su izquierda {2, 5, 1} y al menos K(= 3) elementos a su derecha {3, 4, 0}

Por lo tanto, la cuenta es 2.

Entrada: A[] = {11, 2, 4, 7, 5, 9, 6, 3}, K = 2 
Salida:

Enfoque ingenuo: 
el enfoque más simple para resolver el problema es atravesar la array y, para cada elemento, recorrer todos los elementos a su izquierda y verificar si todos ellos son más pequeños que él o no y atravesar todos los elementos a su derecha para verificar si en menos K elementos son más pequeños que él o no. Por cada elemento que satisfaga las condiciones, aumente el conteo . Finalmente, imprima el valor de count

Complejidad de Tiempo: O(N 2
Espacio Auxiliar: O(1)

Enfoque eficiente: 
el enfoque anterior se puede optimizar aún más mediante el uso de BST de autoequilibrio . Siga los pasos a continuación:  

  • Recorra la array de derecha a izquierda e inserte todos los elementos uno por uno en un árbol AVL
  • Con el árbol AVL, genere una array countSmaller[] que contenga el recuento de elementos más pequeños a la derecha de cada elemento de la array.
  • Recorra la array y para cada i -ésimo elemento , verifique si es el máximo obtenido hasta ahora y countSmaller[i] es mayor o igual que K.
  • Si es así, aumente la cuenta .
  • Imprime el valor final de count como respuesta.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of an AVL Tree Node
struct node {
    int key;
    struct node* left;
    struct node* right;
    int height;
    // Size of the tree rooted
    // with this node
    int size;
};
 
// Utility function to get maximum
// of two integers
int max(int a, int b);
 
// Utility function to get height
// of the tree rooted with N
int height(struct node* N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
// Utility function to find size of
// the tree rooted with N
int size(struct node* N)
{
    if (N == NULL)
        return 0;
    return N->size;
}
 
// Utility function to get maximum
// of two integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Helper function to allocates a
// new node with the given key
struct node* newNode(int key)
{
    struct node* node
        = (struct node*)
            malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    node->size = 1;
    return (node);
}
 
// Utility function to right rotate
// subtree rooted with y
struct node* rightRotate(struct node* y)
{
    struct node* x = y->left;
    struct node* T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left),
                    height(y->right))
                + 1;
    x->height = max(height(x->left),
                    height(x->right))
                + 1;
 
    // Update sizes
    y->size = size(y->left)
              + size(y->right) + 1;
    x->size = size(x->left)
              + size(x->right) + 1;
 
    // Return new root
    return x;
}
 
// Utility function to left rotate
// subtree rooted with x
struct node* leftRotate(struct node* x)
{
    struct node* y = x->right;
    struct node* T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    // Update heights
    x->height = max(height(x->left),
                    height(x->right))
                + 1;
    y->height = max(height(y->left),
                    height(y->right))
                + 1;
 
    // Update sizes
    x->size = size(x->left)
              + size(x->right) + 1;
    y->size = size(y->left)
              + size(y->right) + 1;
 
    // Return new root
    return y;
}
 
// Function to obtain Balance factor
// of node N
int getBalance(struct node* N)
{
    if (N == NULL)
        return 0;
 
    return height(N->left)
           - height(N->right);
}
 
// Function to insert a new key to the
// tree rooted with node
struct node* insert(struct node* node, int key,
                    int* count)
{
    // Perform the normal BST rotation
    if (node == NULL)
        return (newNode(key));
 
    if (key < node->key)
        node->left
            = insert(node->left, key, count);
    else {
        node->right
            = insert(node->right, key, count);
 
        // Update count of smaller elements
        *count = *count + size(node->left) + 1;
    }
 
    // Update height and size of the ancestor
    node->height = max(height(node->left),
                       height(node->right))
                   + 1;
    node->size = size(node->left)
                 + size(node->right) + 1;
 
    // Get the balance factor of the ancestor
    int balance = getBalance(node);
 
    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    return node;
}
 
// Function to generate an array which contains
// count of smaller elements on the right
void constructLowerArray(int arr[],
                         int countSmaller[],
                         int n)
{
    int i, j;
    struct node* root = NULL;
 
    for (i = 0; i < n; i++)
        countSmaller[i] = 0;
 
    // Insert all elements in the AVL Tree
    // and get the count of smaller elements
    for (i = n - 1; i >= 0; i--) {
        root = insert(root, arr[i],
                      &countSmaller[i]);
    }
}
 
// Function to find the number
// of elements which are greater
// than all elements on its left
// and K elements on its right
int countElements(int A[], int n, int K)
{
 
    int count = 0;
 
    // Stores the count of smaller
    // elements on its right
    int* countSmaller
        = (int*)malloc(sizeof(int) * n);
    constructLowerArray(A, countSmaller, n);
 
    int maxi = INT_MIN;
    for (int i = 0; i <= (n - K - 1); i++) {
        if (A[i] > maxi && countSmaller[i] >= K) {
            count++;
            maxi = A[i];
        }
    }
 
    return count;
}
 
// Driver Code
int main()
{
 
    int A[] = { 2, 5, 1, 7, 3, 4, 0 };
    int n = sizeof(A) / sizeof(int);
    int K = 3;
 
    cout << countElements(A, n, K);
 
    return 0;
}
Producción: 

2

 

Complejidad temporal: O(NlogN) 
Espacio auxiliar: O(N)
 

Consulte el artículo completo sobre el número de elementos de la array mayor que todos los elementos a la izquierda y al menos K elementos a la derecha para obtener más detalles.
 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *