Escriba una función para contar el número de elementos más pequeños a la derecha de cada elemento en una array. Dada una array no ordenada arr[] de enteros distintos, construya otra array countSmaller[] tal que countSmaller[i] contenga el recuento de elementos más pequeños en el lado derecho de cada elemento arr[i] en la array.
Ejemplos:
Input: arr[] = {12, 1, 2, 3, 0, 11, 4}
Output: countSmaller[] = {6, 1, 1, 1, 0, 1, 0}
(Corner Cases)
Input: arr[] = {5, 4, 3, 2, 1}
Output: countSmaller[] = {4, 3, 2, 1, 0}
Input: arr[] = {1, 2, 3, 4, 5}
Output: countSmaller[] = {0, 0, 0, 0, 0}
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Método 1 (Simple)
Use dos bucles. El bucle exterior recoge todos los elementos de izquierda a derecha. El ciclo interno itera a través de todos los elementos en el lado derecho del elemento elegido y actualiza countSmaller[].
C++
#include <iostream>
using namespace std;
void constructLowerArray(int arr[], int *countSmaller,
int n)
{
int i, j;
// Initialize all the counts in
// countSmaller array as 0
for(i = 0; i < n; i++)
countSmaller[i] = 0;
for(i = 0; i < n; i++)
{
for(j = i + 1; j < n; j++)
{
if (arr[j] < arr[i])
countSmaller[i]++;
}
}
}
// Utility function that prints
// out an array on a line
void printArray(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
cout << arr[i] << " ";
cout << "\n";
}
// Driver code
int main()
{
int arr[] = { 12, 10, 5, 4, 2,
20, 6, 1, 0, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int *low = (int *)malloc(sizeof(int)*n);
constructLowerArray(arr, low, n);
printArray(low, n);
return 0;
}
// This code is contributed by Hemant Jain
C
void constructLowerArray (int *arr[], int *countSmaller, int n)
{
int i, j;
// initialize all the counts in countSmaller array as 0
for (i = 0; i < n; i++)
countSmaller[i] = 0;
for (i = 0; i < n; i++)
{
for (j = i+1; j < n; j++)
{
if (arr[j] < arr[i])
countSmaller[i]++;
}
}
}
/* Utility function that prints out an array on a line */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{
int arr[] = {12, 10, 5, 4, 2, 20, 6, 1, 0, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int *low = (int *)malloc(sizeof(int)*n);
constructLowerArray(arr, low, n);
printArray(low, n);
return 0;
}
Java
class CountSmaller
{
void constructLowerArray(int arr[], int countSmaller[], int n)
{
int i, j;
// initialize all the counts in countSmaller array as 0
for (i = 0; i < n; i++)
countSmaller[i] = 0;
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[i])
countSmaller[i]++;
}
}
}
/* Utility function that prints out an array on a line */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println("");
}
// Driver program to test above functions
public static void main(String[] args)
{
CountSmaller small = new CountSmaller();
int arr[] = {12, 10, 5, 4, 2, 20, 6, 1, 0, 2};
int n = arr.length;
int low[] = new int[n];
small.constructLowerArray(arr, low, n);
small.printArray(low, n);
}
}
Python3
def constructLowerArray (arr, countSmaller, n): # initialize all the counts in countSmaller array as 0 for i in range(n): countSmaller[i] = 0 for i in range(n): for j in range(i + 1,n): if (arr[j] < arr[i]): countSmaller[i] += 1 # Utility function that prints out an array on a line def printArray(arr, size): for i in range(size): print(arr[i],end=" ") print() # Driver code arr = [12, 10, 5, 4, 2, 20, 6, 1, 0, 2] n = len(arr) low = [0]*n constructLowerArray(arr, low, n) printArray(low, n) # This code is contributed by ApurvaRaj
C#
using System;
class GFG {
static void constructLowerArray(int []arr,
int []countSmaller, int n)
{
int i, j;
// initialize all the counts in
// countSmaller array as 0
for (i = 0; i < n; i++)
countSmaller[i] = 0;
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[i])
countSmaller[i]++;
}
}
}
/* Utility function that prints out
an array on a line */
static void printArray(int []arr, int size)
{
int i;
for (i = 0; i < size; i++)
Console.Write(arr[i] + " ");
Console.WriteLine("");
}
// Driver function
public static void Main()
{
int []arr = new int[]{12, 10, 5, 4,
2, 20, 6, 1, 0, 2};
int n = arr.Length;
int []low = new int[n];
constructLowerArray(arr, low, n);
printArray(low, n);
}
}
// This code is contributed by Sam007
Javascript
<script>
function constructLowerArray(arr, countSmaller, n)
{
let i, j;
// initialize all the counts in
// countSmaller array as 0
for (i = 0; i < n; i++)
countSmaller[i] = 0;
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[i])
countSmaller[i]++;
}
}
}
/* Utility function that prints out
an array on a line */
function printArray(arr, size)
{
let i;
for (i = 0; i < size; i++)
document.write(arr[i] + " ");
document.write("</br>");
}
let arr = [12, 10, 5, 4, 2, 20, 6, 1, 0, 2];
let n = arr.length;
let low = new Array(n);
constructLowerArray(arr, low, n);
printArray(low, n);
</script>
Producción:
8 7 5 4 2 4 3 1 0 0
Complejidad de tiempo: O(n^2)
Espacio auxiliar: O(1)
Método 2 (Usar BST autoequilibrado)
Se puede utilizar un árbol de búsqueda binario autoequilibrado (AVL, Red Black, etc.) para obtener la solución en una complejidad de tiempo O(nLogn). Podemos aumentar estos árboles para que cada Node N contenga el tamaño del subárbol enraizado con N. Hemos utilizado el árbol AVL en la siguiente implementación.
Atravesamos la array de derecha a izquierda e insertamos todos los elementos uno por uno en un árbol AVL. Al insertar una nueva clave en un árbol AVL, primero comparamos la clave con la raíz. Si la clave es mayor que la raíz, entonces es mayor que todos los Nodes del subárbol izquierdo de la raíz. Entonces agregamos el tamaño del subárbol izquierdo al conteo de elementos más pequeños para la clave que se inserta. Seguimos recursivamente el mismo enfoque para todos los Nodes de la raíz.
A continuación se muestra la implementación de C.
C++
#include <iostream>
using namespace std;
#include<stdio.h>
#include<stdlib.h>
// 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;
};
// A utility function to get
// maximum of two integers
int max(int a, int b);
// A utility function to get
// height of the tree rooted with N
int height(struct node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to size
// of the tree of rooted with N
int size(struct node *N)
{
if (N == NULL)
return 0;
return N->size;
}
// A utility function to
// get maximum of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
// Helper function that allocates a
// new node with the given key and
// NULL left and right pointers.
struct node* newNode(int key)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
// New node is initially added at leaf
node->height = 1;
node->size = 1;
return(node);
}
// A 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;
}
// A 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;
}
// Get Balance factor of node N
int getBalance(struct node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Inserts a new key to the tree rotted with
// node. Also, updates *count to contain count
// of smaller elements for the new key
struct node* insert(struct node* node, int key,
int *count)
{
// 1. 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 FOR KEY
*count = *count + size(node->left) + 1;
}
// 2.Update height and size of this ancestor node
node->height = max(height(node->left),
height(node->right)) + 1;
node->size = size(node->left) +
size(node->right) + 1;
// 3. Get the balance factor of this
// ancestor node to check whether this
// node became unbalanced
int balance = getBalance(node);
// If this node becomes unbalanced,
// then there are 4 cases
// 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 the (unchanged) node pointer
return node;
}
// The following function updates the
// countSmaller array to contain count of
// smaller elements on right side.
void constructLowerArray(int arr[], int countSmaller[],
int n)
{
int i, j;
struct node *root = NULL;
// Initialize all the counts in
// countSmaller array as 0
for(i = 0; i < n; i++)
countSmaller[i] = 0;
// Starting from rightmost element,
// insert all elements one by one in
// an AVL tree and get the count of
// smaller elements
for(i = n - 1; i >= 0; i--)
{
root = insert(root, arr[i], &countSmaller[i]);
}
}
// Utility function that prints out an
// array on a line
void printArray(int arr[], int size)
{
int i;
cout << "\n";
for(i = 0; i < size; i++)
cout << arr[i] <<" ";
}
// Driver code
int main()
{
int arr[] = {10, 6, 15, 20, 30, 5, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int *low = (int *)malloc(sizeof(int)*n);
constructLowerArray(arr, low, n);
cout <<"Following is the constructed smaller count array";
printArray(low, n);
return 0;
}
// This code is contributed by Hemant Jain
C
#include<stdio.h>
#include<stdlib.h>
// An AVL tree node
struct node
{
int key;
struct node *left;
struct node *right;
int height;
int size; // size of the tree rooted with this node
};
// A utility function to get maximum of two integers
int max(int a, int b);
// A utility function to get height of the tree rooted with N
int height(struct node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to size of the tree of rooted with N
int size(struct node *N)
{
if (N == NULL)
return 0;
return N->size;
}
// A utility function to get maximum of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
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; // new node is initially added at leaf
node->size = 1;
return(node);
}
// A 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;
}
// A 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;
}
// Get Balance factor of node N
int getBalance(struct node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Inserts a new key to the tree rotted with node. Also, updates *count
// to contain count of smaller elements for the new key
struct node* insert(struct node* node, int key, int *count)
{
/* 1. 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 FOR KEY
*count = *count + size(node->left) + 1;
}
/* 2. Update height and size of this ancestor node */
node->height = max(height(node->left), height(node->right)) + 1;
node->size = size(node->left) + size(node->right) + 1;
/* 3. Get the balance factor of this ancestor node to check whether
this node became unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then there are 4 cases
// 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 the (unchanged) node pointer */
return node;
}
// The following function updates the countSmaller array to contain count of
// smaller elements on right side.
void constructLowerArray (int arr[], int countSmaller[], int n)
{
int i, j;
struct node *root = NULL;
// initialize all the counts in countSmaller array as 0
for (i = 0; i < n; i++)
countSmaller[i] = 0;
// Starting from rightmost element, insert all elements one by one in
// an AVL tree and get the count of smaller elements
for (i = n-1; i >= 0; i--)
{
root = insert(root, arr[i], &countSmaller[i]);
}
}
/* Utility function that prints out an array on a line */
void printArray(int arr[], int size)
{
int i;
printf("\n");
for (i=0; i < size; i++)
printf("%d ", arr[i]);
}
// Driver program to test above functions
int main()
{
int arr[] = {10, 6, 15, 20, 30, 5, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int *low = (int *)malloc(sizeof(int)*n);
constructLowerArray(arr, low, n);
printf("Following is the constructed smaller count array");
printArray(low, n);
return 0;
}
Java
import java.util.*;
class GFG{
// 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;
};
static int []countSmaller ;
static int count;
// A utility function to get
// height of the tree rooted with N
static int height(node N)
{
if (N == null)
return 0;
return N.height;
}
// A utility function to size
// of the tree of rooted with N
static int size(node N)
{
if (N == null)
return 0;
return N.size;
}
// A utility function to
// get maximum of two integers
static int max(int a, int b)
{
return (a > b)? a : b;
}
// Helper function that allocates a
// new node with the given key and
// null left and right pointers.
static node newNode(int key)
{
node node = new node();
node.key = key;
node.left = null;
node.right = null;
// New node is initially added at leaf
node.height = 1;
node.size = 1;
return(node);
}
// A 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 = Math.max(height(y.left),
height(y.right)) + 1;
x.height = Math.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;
}
// A 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 = Math.max(height(x.left),
height(x.right)) + 1;
y.height = Math.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;
}
// Get Balance factor of node N
static int getBalance(node N)
{
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
// Inserts a new key to the tree rotted with
// node. Also, updates *count to contain count
// of smaller elements for the new key
static node insert(node node, int key,
int count)
{
// 1. 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 FOR KEY
countSmaller[count] = countSmaller[count] + size(node.left) + 1;
}
// 2.Update height and size of this ancestor node
node.height = Math.max(height(node.left),
height(node.right)) + 1;
node.size = size(node.left) +
size(node.right) + 1;
// 3. Get the balance factor of this
// ancestor node to check whether this
// node became unbalanced
int balance = getBalance(node);
// If this node becomes unbalanced,
// then there are 4 cases
// 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 the (unchanged) node pointer
return node;
}
// The following function updates the
// countSmaller array to contain count of
// smaller elements on right side.
static void constructLowerArray(int arr[],
int n)
{
int i, j;
node root = null;
// Initialize all the counts in
// countSmaller array as 0
for(i = 0; i < n; i++)
countSmaller[i] = 0;
// Starting from rightmost element,
// insert all elements one by one in
// an AVL tree and get the count of
// smaller elements
for(i = n - 1; i >= 0; i--)
{
root = insert(root, arr[i],i);
}
}
// Utility function that prints out an
// array on a line
static void printArray(int arr[], int size)
{
int i;
System.out.print("\n");
for(i = 0; i < size; i++)
System.out.print(arr[i] +" ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = {10, 6, 15, 20, 30, 5, 7};
int n = arr.length;
countSmaller = new int[n];
constructLowerArray(arr, n);
System.out.print("Following is the constructed smaller count array");
printArray(countSmaller, n);
}
}
// This code is contributed by Rajput-Ji
C#
using System;
public class GFG {
// 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;
};
static int[] countSmaller;
static int count;
// A utility function to get
// height of the tree rooted with N
static int height(node N) {
if (N == null)
return 0;
return N.height;
}
// A utility function to size
// of the tree of rooted with N
static int size(node N) {
if (N == null)
return 0;
return N.size;
}
// A utility function to
// get maximum of two integers
static int max(int a, int b) {
return (a > b) ? a : b;
}
// Helper function that allocates a
// new node with the given key and
// null left and right pointers.
static node newNode(int key) {
node node = new node();
node.key = key;
node.left = null;
node.right = null;
// New node is initially added at leaf
node.height = 1;
node.size = 1;
return (node);
}
// A 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 = Math.Max(height(y.left), height(y.right)) + 1;
x.height = Math.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;
}
// A 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 = Math.Max(height(x.left), height(x.right)) + 1;
y.height = Math.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;
}
// Get Balance factor of node N
static int getBalance(node N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
// Inserts a new key to the tree rotted with
// node. Also, updates *count to contain count
// of smaller elements for the new key
static node insert(node node, int key, int count) {
// 1. 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 FOR KEY
countSmaller[count] = countSmaller[count] + size(node.left) + 1;
}
// 2.Update height and size of this ancestor node
node.height = Math.Max(height(node.left), height(node.right)) + 1;
node.size = size(node.left) + size(node.right) + 1;
// 3. Get the balance factor of this
// ancestor node to check whether this
// node became unbalanced
int balance = getBalance(node);
// If this node becomes unbalanced,
// then there are 4 cases
// 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 the (unchanged) node pointer
return node;
}
// The following function updates the
// countSmaller array to contain count of
// smaller elements on right side.
static void constructLowerArray(int []arr, int n) {
int i, j;
node root = null;
// Initialize all the counts in
// countSmaller array as 0
for (i = 0; i < n; i++)
countSmaller[i] = 0;
// Starting from rightmost element,
// insert all elements one by one in
// an AVL tree and get the count of
// smaller elements
for (i = n - 1; i >= 0; i--) {
root = insert(root, arr[i], i);
}
}
// Utility function that prints out an
// array on a line
static void printArray(int []arr, int size) {
int i;
Console.Write("\n");
for (i = 0; i < size; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main(String[] args) {
int []arr = { 10, 6, 15, 20, 30, 5, 7 };
int n = arr.Length;
countSmaller = new int[n];
constructLowerArray(arr, n);
Console.Write("Following is the constructed smaller count array");
printArray(countSmaller, n);
}
}
// This code is contributed by Rajput-Ji
Producción:
Following is the constructed smaller count array 3 1 2 2 2 0 0
Complejidad de Tiempo: O(nLogn)
Espacio Auxiliar: O(n)
Método 3 (usando BST con 2 campos adicionales)
Otro enfoque para resolver el problema anterior sería usar un árbol de búsqueda binario simple con 2 campos adicionales:
1) para contener los elementos en el lado izquierdo de un Node
2) para almacenar la frecuencia de elemento
En este enfoque, recorremos la array de entrada desde el final hasta el principio y agregamos los elementos al BST.
Al insertar los elementos en el BST, podemos calcular la cantidad de elementos que son elementos menores simplemente calculando la suma de la frecuencia del elemento y la cantidad de elementos al lado izquierdo del Node actual, si nos movemos al lado derecho de el Node actual.
Una vez que colocamos un elemento en su posición correcta, podemos devolver su valor de suma
C++14
#include<bits/stdc++.h>
using namespace std;
// BST node structure
class Node{
public:
int val;
int count;
Node* left;
Node* right;
// Constructor
Node(int num1, int num2)
{
this->val = num1;
this->count = num2;
this->left = this->right = NULL;
}
};
// Function to addNode and find the smaller
// elements on the right side
int addNode(Node*& root, int value,
int countSmaller)
{
// Base case
if (root == NULL)
{
root = new Node(value, 0);
return countSmaller;
}
if (root->val < value)
{
return root->count +
addNode(root->right,
value,
countSmaller + 1);
}
else
{
root->count++;
return addNode(root->left, value,
countSmaller);
}
}
// Driver code
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int data[] = { 10, 6, 15, 20, 30, 5, 7 };
int size = sizeof(data) / sizeof(data[0]);
int ans[size] = {0};
Node* root = NULL;
for(int i = size - 1; i >= 0; i--)
{
ans[i] = addNode(root, data[i], 0);
}
for(int i = 0; i < size; i++)
cout << ans[i] << " ";
return 0;
}
// This code is contributed by divyanshu gupta
Python3
class Node:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
# denotes number of times (frequency)
# an element has occurred.
self.elecount = 1
# denotes the number of nodes on left
# side of the node encountered so far.
self.lcount = 0
class Tree:
def __init__(self,root):
self.root = root
def insert(self,node):
"""This function helps to place an element at
its correct position in the BST and returns
the count of elements which are smaller than
the elements which are already inserted into the BST.
"""
curr = self.root
cnt = 0
while curr!=None:
prev = curr
if node.val>curr.val:
# This step computes the number of elements
# which are less than the current Node.
cnt += (curr.elecount+curr.lcount)
curr=curr.right
elif node.val<curr.val:
curr.lcount+=1
curr=curr.left
else:
prev=curr
prev.elecount+=1
break
if prev.val>node.val:
prev.left = node
elif prev.val<node.val:
prev.right = node
else:
return cnt+prev.lcount
return cnt
def constructArray(arr,n):
t = Tree(Node(arr[-1]))
ans = [0]
for i in range(n-2,-1,-1):
ans.append(t.insert(Node(arr[i])))
return reversed(ans)
# Driver function for above code
def main():
n = 7
arr = [10, 6, 15, 20, 30, 5, 7]
print(" ".join(list(map(str,constructArray(arr,n)))))
if __name__ == "__main__":
main()
# Code Contributed by Tarun Gudipati
Producción:
3 1 2 2 2 0 0
Complejidad de tiempo: O(n 2 ) como paso adicional puede tomar O(n) tiempo.
Espacio auxiliar: O(n)
Cuente los elementos más pequeños en el lado derecho usando Set en C++ STL
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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