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: 2
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: 1
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
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