Reordenar la posición de las palabras en orden alfabético

Dada una array arr[] de strings, la tarea es reordenar lexicográficamente las strings e imprimir sus posiciones en la lista original.
 

Ejemplos: 

Entrada: arr[] = {“zxc”, “efg”, “jkl”} 
Salida: 2 3 1 
La lista ordenada será {“efg”, “jkl”, “zxc”} y sus 
posiciones originales fueron 2, 3 y 1 respectivamente.
 

Entrada: arr[] = {“vivo”, “lugar”, “viaje”, “palabra”, “cielo”} 
Salida: 1 2 5 3 4  

Enfoque: Asigne todas las palabras con un número entero igual a su posición en la array. Luego ordenan lexicográficamente la lista de palabras y se modifican sus posiciones, por lo que se imprimen sus posiciones a partir de la primera palabra de la lista ordenada.

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

// CPP implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the ordering of words
void reArrange(string words[], int n)
{
 
    // Creating list of words and assigning
    // them index numbers
    map<string, int> mp;
    for (int i = 0; i < n; i++)
        mp[words[i]] = i + 1;
 
    // Sort the list of words
    // lexicographically
    sort(words, words + n);
 
    // Print the ordering
    for (int i = 0; i < n; i++)
        cout << mp[words[i]] << " ";
}
 
// Driver Code
int main()
{
    string words[] = { "live", "place", "travel", "word", "sky" };
    int n = sizeof(words) / sizeof(words[0]);
    reArrange(words, n);
}
 
// This code is contributed by
// Surendra_Gangwar

// Java implementation of the approach
import java.util.*;
class GFG {
 
    // Function to print the ordering of words
    static void reArrange(String words[], int n)
    {
 
        // Creating list of words and assigning
        // them index numbers
        HashMap<String, Integer> freq = new HashMap<>();
        for (int i = 0; i < n; i++) {
            freq.put(words[i], (i + 1));
        }
 
        // Sort the list of words
        // lexicographically
        Arrays.sort(words);
 
        // Print the ordering
        for (int i = 0; i < n; i++)
            System.out.print(freq.get(words[i]) + " ");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String words[] = { "live", "place", "travel", "word", "sky" };
        int n = words.length;
        reArrange(words, n);
    }
}

# Python3 implementation of the approach
 
# Function to print the ordering of words
def reArrange(words, n):
    # Creating list of words and assigning
    # them index numbers
    mp = {}
    for i in range(n):
        mp[words[i]] = i + 1
 
    # Sort the list of words
    # lexicographically
    words.sort();
 
    # Print the ordering
    for i in range(n):
        print(mp[words[i]], end = " ")
 
# Driver Code
 
words = [ "live", "place", "travel", "word", "sky" ]
n = len(words)
reArrange(words, n);
 
# This code is contributed by
# Rajnis09

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Function to print the ordering of words
    static void reArrange(String[] words, int n)
    {
 
        // Creating list of words and assigning
        // them index numbers
        Dictionary<String, int> freq = new Dictionary<String, int>();
        for (int i = 0; i < n; i++) {
            freq.Add(words[i], (i + 1));
        }
 
        // Sort the list of words
        // lexicographically
        Array.Sort(words);
 
        // Print the ordering
        for (int i = 0; i < n; i++)
            Console.Write(freq[words[i]] + " ");
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String[] words = { "live", "place", "travel", "word", "sky" };
        int n = words.Length;
        reArrange(words, n);
    }
}
 
// This code contributed by Rajput-Ji

<?php
// PHP implementation of the approach
 
    // Function to print the ordering of words
    function reArrange($words, $n)
    {
 
        // Creating list of words and assigning
        // them index numbers
        $freq = array();
        for ($i = 0; $i < $n; $i++)
        {
            $freq[$words[$i]] = ($i + 1) ;
        }
 
        // Sort the list of words
        // lexicographically
        sort($words);
 
        // Print the ordering
        for ($i = 0; $i < $n; $i++)
            echo $freq[$words[$i]], " " ;
    }
 
    // Driver Code
    $words = array( "live", "place", "travel", "word", "sky" );
    $n = count($words);
    reArrange($words, $n);
     
    // This code is contributed by Ryuga
?>

<script>
 
// Javascript implementation of the approach
 
// Function to print the ordering of words
function reArrange(words, n)
{
 
    // Creating list of words and assigning
    // them index numbers
    var mp = new Map();
    for (var i = 0; i < n; i++)
        mp.set(words[i], i + 1);
 
    // Sort the list of words
    // lexicographically
    words.sort();
 
    // Print the ordering
    for (var i = 0; i < n; i++)
    {
        document.write(mp.get(words[i])+" ");
    }
}
 
// Driver Code
var words = ["live", "place", "travel", "word", "sky"];
var n = words.length;
reArrange(words, n);
 
 
</script>

1 2 5 3 4

Complejidad de tiempo: O(n * log n)

Espacio Auxiliar: O(n)