Programa Java 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: 

Java

// Java program to implement
// the above approach
class GFG{
 
// Structure of an AVL Tree Node
static class Node
{
    int key;
    Node left;
    Node right;
    int height;
     
    // Size of the tree rooted
    // with this Node
    int size;
 
    public Node(int key)
    {
        this.key = key;
        this.left = this.right = null;
        this.size = this.height = 1;
    }
};
 
// Helper class to pass Integer
// as reference
static class RefInteger
{
    Integer value;
     
    public RefInteger(Integer value)
    {
        this.value = value;
    }
}
 
// Utility function to get height
// of the tree rooted with N
static int height(Node N)
{
    if (N == null)
        return 0;
         
    return N.height;
}
 
// Utility function to find size of
// the tree rooted with N
static int size(Node N)
{
    if (N == null)
        return 0;
         
    return N.size;
}
 
// Utility function to get maximum
// of two integers
static int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Utility function to right rotate
// subtree rooted with y
static Node rightRotate(Node y)
{
    Node x = y.left;
    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
static Node leftRotate(Node x)
{
    Node y = x.right;
    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
static int getBalance(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
static Node insert(Node Node, int key,
                   RefInteger count)
{
     
    // Perform the normal BST rotation
    if (Node == null)
        return (new Node(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.value = count.value +
                  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
static void constructLowerArray(int arr[],
     RefInteger[] countSmaller, int n)
{
    int i, j;
    Node root = null;
 
    for(i = 0; i < n; i++)
        countSmaller[i] = new RefInteger(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
static int countElements(int A[], int n,
                         int K)
{
    int count = 0;
 
    // Stores the count of smaller
    // elements on its right
    RefInteger[] countSmaller = new RefInteger[n];
    constructLowerArray(A, countSmaller, n);
 
    int maxi = Integer.MIN_VALUE;
    for(int i = 0; i <= (n - K - 1); i++)
    {
        if (A[i] > maxi &&
            countSmaller[i].value >= K)
        {
            count++;
            maxi = A[i];
        }
    }
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 2, 5, 1, 7, 3, 4, 0 };
    int n = A.length;
    int K = 3;
 
    System.out.println(countElements(A, n, K));
}
}
 
// This code is contributed by sanjeev2552
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 *