Dada una array arr[] que consta de N enteros distintos, la tarea es convertir la array dada en una secuencia de primeros N enteros no negativos, es decir, [0, N – 1] tal que el orden de los elementos sea el mismo, es decir , 0 se coloca en el índice del elemento de array más pequeño, 1 en el índice del segundo elemento más pequeño, y así sucesivamente.
Ejemplos:
Entrada: arr[] = {10, 40, 20}
Salida: 0 2 1Entrada: arr[] = {5, 10, 40, 30, 20}
Salida: 0 1 4 3 2
Enfoque basado en hashing : Consulte la publicación del Conjunto 1 de este artículo para conocer el enfoque basado en hashing.
Complejidad de tiempo: O(N* log N)
Espacio auxiliar: O(N)
Enfoque basado en el vector de pares : Consulte la publicación del Conjunto 2 de este artículo para conocer el enfoque que utiliza el vector de pares .
Complejidad de tiempo: O(N* log N)
Espacio auxiliar: O(N)
Enfoque basado en búsqueda binaria : siga los pasos para resolver el problema:
- Inicialice una array, diga brr[] y almacene todos los elementos de la array arr[] en brr[] .
- Ordene la array brr[] en orden ascendente .
- Recorra la array dada arr[] y para cada elemento, es decir, arr[i] encuentre el límite inferior de arr[i] en la array brr[] e imprima el índice de is como resultado del elemento actual.
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 find the reduced form
// of the given array arr[]
void convert(int arr[], int n)
{
// Stores the sorted form of the
// the given array arr[]
int brr[n];
for (int i = 0; i < n; i++)
brr[i] = arr[i];
// Sort the array brr[]
sort(brr, brr + n);
// Traverse the given array arr[]
for (int i = 0; i < n; i++) {
int l = 0, r = n - 1, mid;
// Perform the Binary Search
while (l <= r) {
// Calculate the value of
// mid
mid = (l + r) / 2;
if (brr[mid] == arr[i]) {
// Print the current
// index and break
cout << mid << ' ';
break;
}
// Update the value of l
else if (brr[mid] < arr[i]) {
l = mid + 1;
}
// Update the value of r
else {
r = mid - 1;
}
}
}
}
// Driver Code
int main()
{
int arr[] = { 10, 20, 15, 12, 11, 50 };
int N = sizeof(arr) / sizeof(arr[0]);
convert(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG
{
// Function to find the reduced form
// of the given array arr[]
static void convert(int arr[], int n)
{
// Stores the sorted form of the
// the given array arr[]
int brr[] = new int[n];
for (int i = 0; i < n; i++)
brr[i] = arr[i];
// Sort the array brr[]
Arrays.sort(brr);
// Traverse the given array arr[]
for (int i = 0; i < n; i++) {
int l = 0, r = n - 1, mid;
// Perform the Binary Search
while (l <= r) {
// Calculate the value of
// mid
mid = (l + r) / 2;
if (brr[mid] == arr[i]) {
// Print the current
// index and break
System.out.print(mid + " ");
break;
}
// Update the value of l
else if (brr[mid] < arr[i]) {
l = mid + 1;
}
// Update the value of r
else {
r = mid - 1;
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 10, 20, 15, 12, 11, 50 };
int N = arr.length;
convert(arr, N);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to find the reduced form # of the given array arr[] def convert(arr, n): # Stores the sorted form of the # the given array arr[] brr = [i for i in arr] # Sort the array brr[] brr = sorted(brr) # Traverse the given array arr[] for i in range(n): l, r, mid = 0, n - 1, 0 # Perform the Binary Search while (l <= r): # Calculate the value of # mid mid = (l + r) // 2 if (brr[mid] == arr[i]): # Print the current # index and break print(mid,end=" ") break # Update the value of l elif (brr[mid] < arr[i]): l = mid + 1 # Update the value of r else: r = mid - 1 # Driver Code if __name__ == '__main__': arr=[10, 20, 15, 12, 11, 50] N = len(arr) convert(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the reduced form
// of the given array arr[]
static void convert(int[] arr, int n)
{
// Stores the sorted form of the
// the given array arr[]
int[] brr = new int[n];
for(int i = 0; i < n; i++)
brr[i] = arr[i];
// Sort the array brr[]
Array.Sort(brr);
// Traverse the given array arr[]
for(int i = 0; i < n; i++)
{
int l = 0, r = n - 1, mid;
// Perform the Binary Search
while (l <= r)
{
// Calculate the value of
// mid
mid = (l + r) / 2;
if (brr[mid] == arr[i])
{
// Print the current
// index and break
Console.Write(mid + " ");
break;
}
// Update the value of l
else if (brr[mid] < arr[i])
{
l = mid + 1;
}
// Update the value of r
else
{
r = mid - 1;
}
}
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 10, 20, 15, 12, 11, 50 };
int N = arr.Length;
convert(arr, N);
}
}
// This code is contributed by ukasp
Javascript
<script>
// javascript program for the above approach
// Function to find the reduced form
// of the given array arr[]
function convert(arr, n)
{
// Stores the sorted form of the
// the given array arr[]
var brr = Array(n).fill(0);
var i;
for (i = 0; i < n; i++)
brr[i] = arr[i];
// Sort the array brr[]
brr.sort();
// Traverse the given array arr[]
for (i = 0; i < n; i++) {
var l = 0, r = n - 1, mid;
// Perform the Binary Search
while (l <= r) {
// Calculate the value of
// mid
mid = parseInt((l + r) / 2,10);
if (brr[mid] == arr[i]) {
// Print the current
// index and break
document.write(mid + ' ');
break;
}
// Update the value of l
else if (brr[mid] < arr[i]) {
l = mid + 1;
}
// Update the value of r
else {
r = mid - 1;
}
}
}
}
// Driver Code
var arr = [10, 20, 15, 12, 11, 50];
var N = arr.length;
convert(arr, N);
// This code is contributed by SURENDRA_GANGWAR.
</script>
0 4 3 2 1 5
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shandilraunak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA