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:
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; }
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