Dada una array arr[] de N enteros, la tarea es contar el número de elementos más pequeños en el lado derecho para cada uno de los elementos de la array
Ejemplos:
Entrada: arr[] = {6, 3, 7, 2}
Salida: 2, 1, 1, 0
Explicación:
Elementos más pequeños después de 6 = 2 [3, 2]
Elementos más pequeños después de 3 = 1 [2]
Elementos más pequeños después de 7 = 1 [2]
Elementos más pequeños después de 2 = 0Entrada: arr[] = {6, 19, 111, 13}
Salida: 0, 1, 1, 0
Explicación:
Elementos más pequeños después de 6 = 0
Elementos más pequeños después de 19 = 1 [13]
Elementos más pequeños después de 111 = 1 [13]
Elementos más pequeños después de 13 = 0
Enfoque:
use la idea de la ordenación por fusión al momento de fusionar dos arrays. Cuando el elemento de índice más alto es menor que el elemento de índice más bajo, representa que el elemento de índice más alto es más pequeño que todos los elementos después de ese índice más bajo porque la parte izquierda ya está ordenada. Por lo tanto, sume todos los elementos después del elemento de índice inferior para el conteo requerido.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the count of
// smaller elements on right side of
// each element in an Array
// using Merge sort
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int ans[N];
// Utility function that merge the array
// and count smaller element on right side
void merge(pair<int, int> a[], int start,
int mid, int end)
{
pair<int, int> f[mid - start + 1],
s[end - mid];
int n = mid - start + 1;
int m = end - mid;
for(int i = start; i <= mid; i++)
f[i - start] = a[i];
for(int i = mid + 1; i <= end; i++)
s[i - mid - 1] = a[i];
int i = 0, j = 0, k = start;
int cnt = 0;
// Loop to store the count of smaller
// Elements on right side when both
// Array have some elements
while(i < n && j < m)
{
if (f[i].second <= s[j].second)
{
ans[f[i].first] += cnt;
a[k++] = f[i++];
}
else
{
cnt++;
a[k++] = s[j++];
}
}
// Loop to store the count of smaller
// elements in right side when only
// left array have some element
while(i < n)
{
ans[f[i].first] += cnt;
a[k++] = f[i++];
}
// Loop to store the count of smaller
// elements in right side when only
// right array have some element
while(j < m)
{
a[k++] = s[j++];
}
}
// Function to invoke merge sort.
void mergesort(pair<int, int> item[],
int low, int high)
{
if (low >= high)
return;
int mid = (low + high) / 2;
mergesort(item, low, mid);
mergesort(item, mid + 1, high);
merge(item, low, mid, high);
}
// Utility function that prints
// out an array on a line
void print(int arr[], int n)
{
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver code.
int main()
{
int arr[] = { 10, 9, 5, 2, 7,
6, 11, 0, 2 };
int n = sizeof(arr) / sizeof(int);
pair<int, int> a[n];
memset(ans, 0, sizeof(ans));
for(int i = 0; i < n; i++)
{
a[i].second = arr[i];
a[i].first = i;
}
mergesort(a, 0, n - 1);
print(ans, n);
return 0;
}
// This code is contributed by rishabhtyagi2306
Java
// Java program to find the count of smaller elements
// on right side of each element in an Array
// using Merge sort
import java.util.*;
public class GFG {
// Class for storing the index
// and Value pairs
class Item {
int val;
int index;
public Item(int val, int index)
{
this.val = val;
this.index = index;
}
}
// Function to count the number of
// smaller elements on right side
public ArrayList<Integer> countSmall(int[] A)
{
int len = A.length;
Item[] items = new Item[len];
for (int i = 0; i < len; i++) {
items[i] = new Item(A[i], i);
}
int[] count = new int[len];
mergeSort(items, 0, len - 1, count);
ArrayList<Integer> res = new ArrayList<>();
for (int i : count) {
res.add(i);
}
return res;
}
// Function for Merge Sort
private void mergeSort(Item[] items,
int low, int high,
int[] count)
{
if (low >= high) {
return;
}
int mid = low + (high - low) / 2;
mergeSort(items, low, mid, count);
mergeSort(items, mid + 1, high, count);
merge(items, low, mid, mid + 1, high, count);
}
// Utility function that merge the array
// and count smaller element on right side
private void merge(Item[] items, int low,
int lowEnd, int high,
int highEnd, int[] count)
{
int m = highEnd - low + 1;
Item[] sorted = new Item[m];
int rightCounter = 0;
int lowPtr = low, highPtr = high;
int index = 0;
// Loop to store the count of smaller
// Elements on right side when both
// Array have some elements
while (lowPtr <= lowEnd && highPtr <= highEnd) {
if (items[lowPtr].val > items[highPtr].val) {
rightCounter++;
sorted[index++] = items[highPtr++];
}
else {
count[items[lowPtr].index] += rightCounter;
sorted[index++] = items[lowPtr++];
}
}
// Loop to store the count of smaller
// elements in right side when only
// left array have some element
while (lowPtr <= lowEnd) {
count[items[lowPtr].index] += rightCounter;
sorted[index++] = items[lowPtr++];
}
// Loop to store the count of smaller
// elements in right side when only
// right array have some element
while (highPtr <= highEnd) {
sorted[index++] = items[highPtr++];
}
System.arraycopy(sorted, 0, items, low, m);
}
// Utility function that prints
// out an array on a line
void printArray(ArrayList<Integer> countList)
{
for (Integer i : countList)
System.out.print(i + " ");
System.out.println("");
}
// Driver Code
public static void main(String[] args)
{
GFG cntSmall = new GFG();
int arr[] = { 10, 9, 5, 2, 7, 6, 11, 0, 2 };
int n = arr.length;
ArrayList<Integer> countList
= cntSmall.countSmall(arr);
cntSmall.printArray(countList);
}
}
Python3
# Python3 program to find the count of # smaller elements on right side of # each element in an Array # using Merge sort N = 100001 ans = [0] * N # Utility function that merge the array # and count smaller element on right side def merge(a, start, mid, end): f = [0] * (mid - start + 1) s = [0] * (end - mid) n = mid - start + 1 m = end - mid for i in range(start, mid + 1): f[i - start] = a[i] for i in range ( mid + 1, end + 1): s[i - mid - 1] = a[i] i = 0 j = 0 k = start cnt = 0 # Loop to store the count of smaller # Elements on right side when both # Array have some elements while (i < n and j < m): if (f[i][1] <= s[j][1]): ans[f[i][0]] += cnt a[k] = f[i] k += 1 i += 1 else: cnt += 1 a[k] = s[j] k += 1 j += 1 # Loop to store the count of smaller # elements in right side when only # left array have some element while (i < n): ans[f[i][0]] += cnt a[k] = f[i]; k += 1 i += 1 # Loop to store the count of smaller # elements in right side when only # right array have some element while (j < m): a[k] = s[j] k += 1 j += 1 # Function to invoke merge sort. def mergesort(item, low, high): if (low >= high): return mid = (low + high) // 2 mergesort(item, low, mid) mergesort(item, mid + 1, high) merge(item, low, mid, high) # Utility function that prints # out an array on a line def print_(arr, n): for i in range(n): print(arr[i], end = " ") # Driver code. if __name__ == "__main__": arr = [ 10, 9, 5, 2, 7, 6, 11, 0, 2 ] n = len(arr) a = [[0 for x in range(2)] for y in range(n)] for i in range(n): a[i][1] = arr[i] a[i][0] = i mergesort(a, 0, n - 1) print_(ans, n) # This code is contributed by chitranayal
C#
// C# program to find the count of smaller elements
// on right side of each element in an Array
// using Merge sort
using System;
using System.Collections.Generic;
class GFG
{
// Class for storing the index
// and Value pairs
public class Item
{
public int val;
public int index;
public Item(int val, int index)
{
this.val = val;
this.index = index;
}
}
// Function to count the number of
// smaller elements on right side
public List<int> countSmall(int[] A)
{
int len = A.Length;
Item[] items = new Item[len];
for (int i = 0; i < len; i++)
{
items[i] = new Item(A[i], i);
}
int[] count = new int[len];
mergeSort(items, 0, len - 1, count);
List<int> res = new List<int>();
foreach (int i in count)
{
res.Add(i);
}
return res;
}
// Function for Merge Sort
private void mergeSort(Item[] items,
int low, int high,
int[] count)
{
if (low >= high)
{
return;
}
int mid = low + (high - low) / 2;
mergeSort(items, low, mid, count);
mergeSort(items, mid + 1, high, count);
merge(items, low, mid, mid + 1, high, count);
}
// Utility function that merge the array
// and count smaller element on right side
private void merge(Item[] items, int low,
int lowEnd, int high,
int highEnd, int[] count)
{
int m = highEnd - low + 1;
Item[] sorted = new Item[m];
int rightCounter = 0;
int lowPtr = low, highPtr = high;
int index = 0;
// Loop to store the count of smaller
// Elements on right side when both
// Array have some elements
while (lowPtr <= lowEnd && highPtr <= highEnd)
{
if (items[lowPtr].val > items[highPtr].val)
{
rightCounter++;
sorted[index++] = items[highPtr++];
}
else
{
count[items[lowPtr].index] += rightCounter;
sorted[index++] = items[lowPtr++];
}
}
// Loop to store the count of smaller
// elements in right side when only
// left array have some element
while (lowPtr <= lowEnd)
{
count[items[lowPtr].index] += rightCounter;
sorted[index++] = items[lowPtr++];
}
// Loop to store the count of smaller
// elements in right side when only
// right array have some element
while (highPtr <= highEnd)
{
sorted[index++] = items[highPtr++];
}
Array.Copy(sorted, 0, items, low, m);
}
// Utility function that prints
// out an array on a line
void printArray(List<int> countList)
{
foreach (int i in countList)
Console.Write(i + " ");
Console.WriteLine("");
}
// Driver Code
public static void Main(String[] args)
{
GFG cntSmall = new GFG();
int []arr = { 10, 9, 5, 2, 7, 6, 11, 0, 2 };
int n = arr.Length;
List<int> countList
= cntSmall.countSmall(arr);
cntSmall.printArray(countList);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find the count of
// smaller elements on right side of each
// element in an Array using Merge sort
let N = 100001;
let ans = new Array(N);
// Utility function that merge the array
// and count smaller element on right side
function merge(a, start, mid, end)
{
let f = new Array((mid - start + 1));
let s = new Array(end - mid);
let n = mid - start + 1;
let m = end - mid;
for(let i = start; i <= mid; i++)
f[i - start] = a[i];
for(let i = mid + 1; i <= end; i++)
s[i - mid - 1] = a[i];
let i = 0, j = 0, k = start;
let cnt = 0;
// Loop to store the count of smaller
// Elements on right side when both
// Array have some elements
while(i < n && j < m)
{
if (f[i][1] <= s[j][1])
{
ans[f[i][0]] += cnt;
a[k++] = f[i++];
}
else
{
cnt++;
a[k++] = s[j++];
}
}
// Loop to store the count of smaller
// elements in right side when only
// left array have some element
while(i < n)
{
ans[f[i][0]] += cnt;
a[k++] = f[i++];
}
// Loop to store the count of smaller
// elements in right side when only
// right array have some element
while(j < m)
{
a[k++] = s[j++];
}
}
// Function to invoke merge sort.
function mergesort(item, low, high)
{
if (low >= high)
return;
let mid = Math.floor((low + high) / 2);
mergesort(item, low, mid);
mergesort(item, mid + 1, high);
merge(item, low, mid, high);
}
// Utility function that prints
// out an array on a line
function print(arr, n)
{
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver Code
let arr = [ 10, 9, 5, 2, 7, 6, 11, 0, 2 ];
let n = arr.length;
let a = new Array(n);
for(let i = 0; i < a.length; i++)
{
a[i] = new Array(2);
}
for(let i = 0; i < ans.length; i++)
{
ans[i] = 0;
}
for(let i = 0; i < n; i++)
{
a[i][1] = arr[i];
a[i][0] = i;
}
mergesort(a, 0, n - 1);
print(ans, n);
// This code is contributed by rag2127
</script>
Producción
7 6 3 1 3 2 2 0 0
Complejidad de tiempo: O(N log N)
Artículo relacionado: Cuente los elementos más pequeños en el lado derecho