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>
3 4 0 0 2
Complejidad de Tiempo: O(N 2 )
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 5 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>
3 4 0 0 2
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(10 5 )