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;
}
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 referencee
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
Python3
# Python program to implement # the above approach import sys # Structure of an AVL Tree Node class Node: def __init__(self, key): self.key = key; self.left = None; self.right = None; self.height = 1; self.size = 1; # Helper class to pass Integer # as referencee class RefInteger: def __init__(self, data): self.value = data; # Utility function to get height # of the tree rooted with N def height(N): if (N == None): return 0; return N.height; # Utility function to find size of # the tree rooted with N def size(N): if (N == None): return 0; return N.size; # Utility function to get maximum # of two integers def max(a, b): if(a>b): return a; else: return b; # Utility function to right rotate # subtree rooted with y def rightRotate(y): x = y.left; 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 def leftRotate(x): y = x.right; 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 def getBalance(N): if (N == None): return 0; return height(N.left) - height(N.right); # Function to insert a new key to the # tree rooted with Node def insert(node, key, count): # Perform the normal BST rotation if (node == None): return 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 balance = getBalance(node); # Left Left Case if (balance > 1 and key < node.left.key): return rightRotate(node); # Right Right Case if (balance < -1 and key > node.right.key): return leftRotate(node); # Left Right Case if (balance > 1 and key > node.left.key): node.left = leftRotate(node.left); return rightRotate(node); # Right Left Case if (balance < -1 and 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 def constructLowerArray(arr, countSmaller, n): root = None; for i in range(n): countSmaller[i] = RefInteger(0); # Insert all elements in the AVL Tree # and get the count of smaller elements for i in range(n - 1, -1,-1): 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 def countElements(A, n, K): count = 0; # Stores the count of smaller # elements on its right countSmaller = [0 for i in range(n)]; constructLowerArray(A, countSmaller, n); maxi = -sys.maxsize; for i in range(n - K): if (A[i] > maxi and countSmaller[i].value >= K): count += 1; maxi = A[i]; return count; # Driver Code if __name__ == '__main__': A = [ 2, 5, 1, 7, 3, 4, 0 ]; n = len(A); K = 3; print(countElements(A, n, K)); # This code is contributed by Rajput-Ji
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Structure of an AVL Tree Node
public class Node
{
public int key;
public Node left;
public Node right;
public int height;
// Size of the tree rooted
// with this Node
public int size;
public Node(int key)
{
this.key = key;
this.left = this.right = null;
this.size = this.height = 1;
}
};
// Helper class to pass int
// as referencee
public class Refint
{
public int value;
public Refint(int 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,
Refint 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,
Refint[] countSmaller, int n)
{
int i;
//int j;
Node root = null;
for(i = 0; i < n; i++)
countSmaller[i] = new Refint(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
Refint[] countSmaller = new Refint[n];
constructLowerArray(A, countSmaller, n);
int maxi = int.MinValue;
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;
Console.WriteLine(countElements(A, n, K));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// javascript program to implement
// the above approach
// Structure of an AVL Tree Node
class Node
{
// Size of the tree rooted
// with this Node
constructor(key) {
this.key = key;
this.left = this.right = null;
this.size = this.height = 1;
}
};
// Helper class to pass Integer
// as referencee
class RefInteger {
constructor(value) {
this.value = value;
}
}
// Utility function to get height
// of the tree rooted with N
function height(N) {
if (N == null)
return 0;
return N.height;
}
// Utility function to find size of
// the tree rooted with N
function size(N) {
if (N == null)
return 0;
return N.size;
}
// Utility function to get maximum
// of two integers
function max(a , b) {
return (a > b) ? a : b;
}
// Utility function to right rotate
// subtree rooted with y
function rightRotate(y)
{
var x = y.left;
var 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
function leftRotate(x)
{
var y = x.right;
var 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
function getBalance(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
function insert(node , key, 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
var 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
function constructLowerArray(arr, countSmaller , n)
{
var i, j;
var 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
function countElements(A , n , K) {
var count = 0;
// Stores the count of smaller
// elements on its right
var countSmaller = [];
constructLowerArray(A, countSmaller, n);
var maxi = Number.MIN_VALUE;
for (i = 0; i <= (n - K - 1); i++) {
if (A[i] > maxi && countSmaller[i].value >= K) {
count++;
maxi = A[i];
}
}
return count;
}
// Driver Code
var A = [ 2, 5, 1, 7, 3, 4, 0 ];
var n = A.length;
var K = 3;
document.write(countElements(A, n, K));
// This code is contributed by Rajput-Ji
</script>
Producción:
2
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kritirikhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA