Ordenar strings en base a su parte numérica

Dada una oración S de tamaño N donde cada palabra es una concatenación de una parte numérica seguida de un grupo de caracteres. La tarea es ordenar las palabras en orden creciente de su parte numérica.

Ejemplos:

Entrada: S = «24 asombrosos 7 codificadores 11 son»
Salida: los codificadores son asombrosos
Explicación: el orden de los valores numéricos es 7, 11, 24. 
Por lo tanto, están ordenados en consecuencia

Entrada: S = “19-Amo 10-I 2001-cricket”
Salida: Me encanta el cricket

Enfoque: El enfoque de la solución se basa en el concepto de min-heap . Divide las strings en espacios y colócalas en el montón. Por último, sáquelos del montón e imprímalos en orden. Eso dará la solución deseada.

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

// C++ code to implement the approach
#include <bits/stdc++.h>
#include <boost/algorithm/string.hpp>
using namespace std;
 
// For arranging words on the basis
// of numeric part
 
// Function to arrange the sentence
string solve(string str)
{
     
    vector<string> arr;
    boost::split(arr, str, boost::is_any_of(" "));
     
    priority_queue<pair<int,string>> pq;
    for(int i = 0; i < arr.size(); i++)
    {
        string s = arr[i];
        string N = "";
        int a = 0;
        while(s[a] != '-')
        {
            N += s[a];
            a += 1;
        }
        int num = stoi(N);
        string word = arr[i].substr(a + 1);
        pq.push(make_pair(num, word));
    }
     
    string sb = "";
    while (0 < pq.size())
    {    sb = pq.top().second + " "+sb;
        pq.pop();
    }
    return sb;
}
 
// Driver code
int main()
{
    string S = "19-Love 10-I 2001-cricket";
 
    string ans = solve(S);
    cout<<ans;
}
 
// This code is contributed by Pushpesh raj

// Java code to implement above approach
import java.util.*;
 
class GFG {
 
    // For arranging words on the basis
    // of numeric part
    public static class pair
        implements Comparable<pair> {
 
        int num;
        String word;
 
        pair(int num, String word)
        {
            this.num = num;
            this.word = word;
        }
        public int compareTo(pair o)
        {
            return this.num - o.num;
        }
    }
 
    // Function to arrange the sentence
    public static String solve(String str)
    {
        String[] arr = str.split(" ");
        PriorityQueue<pair> pq
            = new PriorityQueue<>();
        for (int i = 0; i < arr.length;
             i++) {
            String s = arr[i];
            String N = "";
            int a = 0;
            while (s.charAt(a) != '-') {
                N += s.charAt(a);
                a++;
            }
            int num = Integer.parseInt(N);
            String word = s.substring(a + 1);
            pq.add(new pair(num, word));
        }
 
        StringBuilder sb
            = new StringBuilder();
        while (pq.size() > 0) {
            pair p = pq.remove();
            sb.append(p.word);
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String S = "19-Love 10-I 2001-cricket";
 
        String ans = solve(S);
        System.out.println(ans);
    }
}

# python3 code for the above approach
 
# For arranging words on the basis
# of numeric part
 
# Function to arrange the sentence
def solve(str):
    arr = str.split(" ")
 
    pq = []
    for i in range(0, len(arr)):
        s = arr[i]
        N = ""
        a = 0
        while (s[a] != '-'):
            N += s[a]
            a += 1
 
        num = int(N)
        word = s[a + 1:]
 
        pq.append([num, word])
 
    pq.sort()
 
    sb = ""
    k = 0
    while (k < len(pq)):
        sb += pq[k][1] + " "
        k
        k += 1
 
    return sb
 
# Driver code
if __name__ == "__main__":
 
    S = "19-Love 10-I 2001-cricket"
 
    ans = solve(S)
    print(ans)
 
    # This code is contributed by rakeshsahni

<script>
       // JavaScript code for the above approach
 
 
       // For arranging words on the basis
       // of numeric part
 
 
       // Function to arrange the sentence
       function solve(str) {
           let arr = str.split(" ");
 
           let pq = []
           for (let i = 0; i < arr.length;
               i++) {
               let s = arr[i];
               let N = "";
               let a = 0;
               while (s.charAt(a) != '-') {
                   N += s.charAt(a);
                   a++;
               }
               let num = parseInt(N);
               let word = s.slice(a + 1);
 
               pq.push({ 'first': num, 'second': word });
           }
           pq.sort(function (a, b) { return a.first - b.first })
 
           let sb = "";
           let k = 0;
           while (k < pq.length) {
               sb += pq[k].second + " ";
               k++;
           }
 
           return sb
       }
 
       // Driver code
       let S = "19-Love 10-I 2001-cricket";
 
       let ans = solve(S);
       document.write(ans);
 
      // This code is contributed by Potta Lokesh
   </script>

I Love cricket

Complejidad temporal: O(N)
Espacio auxiliar: O(N)