Cuente los elementos más pequeños presentes en la array para cada elemento de la array

Dada una array arr[] que consta de N enteros, la tarea es para cada elemento de la array, digamos arr[i] , es encontrar la cantidad de elementos de la array que son más pequeños que arr[i] .

Ejemplos:

Entrada: arr[] = {3, 4, 1, 1, 2}
Salida: 3 4 0 0 2
Explicación:
Los elementos que son más pequeños que arr[0](= 3) son {1, 1, 2}. Por lo tanto, la cuenta es 3.
Los elementos que son más pequeños que arr[1](= 4) son {1, 1, 2, 3}. Por lo tanto, la cuenta es 4.
Los elementos arr[2](= 1) y arr[3](= 1) son los más pequeños posibles. Por lo tanto, la cuenta es 0.
Los elementos que son más pequeños que arr[4](= 2) son {1, 1}. Por lo tanto, la cuenta es 2.

Entrada: arr[] = {1, 2, 3, 4}
Salida: 0 1 2 3

Enfoque ingenuo: el enfoque más simple es atravesar la array y, para cada elemento de la array, contar la cantidad de elementos de la array que son más pequeños que ellos e imprimir los recuentos obtenidos.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count for each array
// element, the number of elements
// that are smaller than that element
void smallerNumbers(int arr[], int N)
{
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Stores the count
        int count = 0;
 
        // Traverse the array
        for (int j = 0; j < N; j++) {
 
            // Increment count
            if (arr[j] < arr[i]) {
                count++;
            }
        }
 
        // Print the count of smaller
        // elements for the current element
        cout << count << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 4, 1, 1, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    smallerNumbers(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to count for each array
// element, the number of elements
// that are smaller than that element
static void smallerNumbers(int arr[], int N)
{
     
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // Stores the count
        int count = 0;
 
        // Traverse the array
        for(int j = 0; j < N; j++)
        {
             
            // Increment count
            if (arr[j] < arr[i])
            {
                count++;
            }
        }
 
        // Print the count of smaller
        // elements for the current element
        System.out.print(count + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 3, 4, 1, 1, 2 };
    int N = arr.length;
 
    smallerNumbers(arr, N);
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
 
# Function to count for each array
# element, the number of elements
# that are smaller than that element
def smallerNumbers(arr, N):
 
    # Traverse the array
    for i in range(N):
 
        # Stores the count
        count = 0
 
        # Traverse the array
        for j in range(N):
 
            # Increment count
            if (arr[j] < arr[i]):
                count += 1
 
        # Print the count of smaller
        # elements for the current element
        print(count, end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    arr = [3, 4, 1, 1, 2]
    N = len(arr)
 
    smallerNumbers(arr, N)
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
public class GFG
{
 
  // Function to count for each array
  // element, the number of elements
  // that are smaller than that element
  static void smallerNumbers(int[] arr, int N)
  {
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
 
      // Stores the count
      int count = 0;
 
      // Traverse the array
      for(int j = 0; j < N; j++)
      {
 
        // Increment count
        if (arr[j] < arr[i])
        {
          count++;
        }
      }
 
      // Print the count of smaller
      // elements for the current element
      Console.Write(count + " ");
    }
  }
 
  // Driver Code
  static public void Main()
  {
    int[] arr = { 3, 4, 1, 1, 2 };
    int N = arr.Length;
 
    smallerNumbers(arr, N);
  }
}
 
// This code is contributed by sanjoy_62,

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to count for each array
// element, the number of elements
// that are smaller than that element
function smallerNumbers(arr, N)
{
    var i;
    // Traverse the array
    for(i = 0; i < N; i++) {
 
        // Stores the count
        var count = 0;
 
        // Traverse the array
        for (j = 0; j < N; j++) {
 
            // Increment count
            if (arr[j] < arr[i]) {
                count += 1;
            }
        }
 
        // Print the count of smaller
        // elements for the current element
        document.write(count + " ");
    }
}
 
// Driver Code
    var arr = [3, 4, 1, 1, 2]
    var N = arr.length;
 
    smallerNumbers(arr, N);
 
</script>

Producción:

3 4 0 0 2

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de Hashing . Siga los pasos a continuación para resolver el problema:

Inicialice una array auxiliar hash[] de tamaño 10 ⁵ e inicialice todos los elementos de la array con 0 para almacenar la frecuencia de cada elemento de la array .
Recorre la array dada arr[] e incrementa la frecuencia de arr[i] en 1 en la array hash[] como hash[arr[i]]++ .
Encuentre la suma del prefijo de la array hash[] .
Nuevamente, recorra la array dada y para cada elemento de la array arr[] , imprima el valor de hash[arr[i] – 1] como el recuento de elementos más pequeños.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count for each array
// element, the number of elements
// that are smaller than that element
void smallerNumbers(int arr[], int N)
{
    // Stores the frequencies
    // of array elements
    int hash[100000] = { 0 };
 
    // Traverse the array
    for (int i = 0; i < N; i++)
 
        // Update frequency of arr[i]
        hash[arr[i]]++;
 
    // Initialize sum with 0
    int sum = 0;
 
    // Compute prefix sum of the array hash[]
    for (int i = 1; i < 100000; i++) {
        hash[i] += hash[i - 1];
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
 
        // If current element is 0
        if (arr[i] == 0) {
            cout << "0";
            continue;
        }
 
        // Print the resultant count
        cout << hash[arr[i] - 1]
             << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 4, 1, 1, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    smallerNumbers(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to count for each array
// element, the number of elements
// that are smaller than that element
static void smallerNumbers(int arr[], int N)
{
     
    // Stores the frequencies
    // of array elements
    int hash[] = new int[100000];
 
    // Traverse the array
    for(int i = 0; i < N; i++)
 
        // Update frequency of arr[i]
        hash[arr[i]]++;
 
    // Initialize sum with 0
    int sum = 0;
 
    // Compute prefix sum of the array hash[]
    for(int i = 1; i < 100000; i++)
    {
        hash[i] += hash[i - 1];
    }
 
    // Traverse the array arr[]
    for(int i = 0; i < N; i++)
    {
         
        // If current element is 0
        if (arr[i] == 0)
        {
            System.out.println("0");
            continue;
        }
 
        // Print the resultant count
        System.out.print(hash[arr[i] - 1] + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 3, 4, 1, 1, 2 };
    int N = arr.length;
 
    smallerNumbers(arr, N);
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
 
# Function to count for each array
# element, the number of elements
# that are smaller than that element
def smallerNumbers(arr, N):
 
    # Stores the frequencies
    # of array elements
    hash = [0] * 100000
 
    # Traverse the array
    for i in range(N):
 
        # Update frequency of arr[i]
        hash[arr[i]] += 1
 
    # Initialize sum with 0
    sum = 0
 
    # Compute prefix sum of the array hash[]
    for i in range(1, 100000):
        hash[i] += hash[i - 1]
 
    # Traverse the array arr[]
    for i in range(N):
 
        # If current element is 0
        if (arr[i] == 0):
            print("0")
            continue
 
        # Print the resultant count
        print(hash[arr[i] - 1], end = " ")
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 3, 4, 1, 1, 2 ]
    N = len(arr)
 
    smallerNumbers(arr, N)
 
# This code is contributed by AnkThon

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count for each array
// element, the number of elements
// that are smaller than that element
static void smallerNumbers(int []arr, int N)
{
     
    // Stores the frequencies
    // of array elements
    int []hash = new int[100000];
 
    // Traverse the array
    for(int i = 0; i < N; i++)
     
        // Update frequency of arr[i]
        hash[arr[i]]++;
 
    // Initialize sum with 0
    //int sum = 0;
 
    // Compute prefix sum of the array hash[]
    for(int i = 1; i < 100000; i++)
    {
        hash[i] += hash[i - 1];
    }
 
    // Traverse the array arr[]
    for(int i = 0; i < N; i++)
    {
         
        // If current element is 0
        if (arr[i] == 0)
        {
            Console.WriteLine("0");
            continue;
        }
 
        // Print the resultant count
        Console.Write(hash[arr[i] - 1] + " ");
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    int []arr = { 3, 4, 1, 1, 2 };
    int N = arr.Length;
 
    smallerNumbers(arr, N);
}
}
 
// This code is contributed by AnkThon

Javascript

<script>
 
    // JavaScript program for the above approach
     
    // Function to count for each array
    // element, the number of elements
    // that are smaller than that element
    function smallerNumbers(arr, N)
    {
 
        // Stores the frequencies
        // of array elements
        let hash = new Array(100000);
        hash.fill(0);
 
        // Traverse the array
        for(let i = 0; i < N; i++)
 
            // Update frequency of arr[i]
            hash[arr[i]]++;
 
        // Initialize sum with 0
        let sum = 0;
 
        // Compute prefix sum of the array hash[]
        for(let i = 1; i < 100000; i++)
        {
            hash[i] += hash[i - 1];
        }
 
        // Traverse the array arr[]
        for(let i = 0; i < N; i++)
        {
 
            // If current element is 0
            if (arr[i] == 0)
            {
                document.write("0" + "</br>");
                continue;
            }
 
            // Print the resultant count
            document.write(hash[arr[i] - 1] + " ");
        }
    }
     
    let arr = [ 3, 4, 1, 1, 2 ];
    let N = arr.length;
  
    smallerNumbers(arr, N);
     
</script>

Producción:

3 4 0 0 2

Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(10 ⁵ )

Publicación traducida automáticamente

Artículo escrito por ketaki888 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta