Comment trier un tableau de chaînes qui contient des nombres négatifs et positifs en c++.?




arrays string (2)

Une autre solution consiste à implémenter votre propre fonction de comparaison:

  • Vérifiez le premier caractère des deux chaînes. Si l'une commence par un chiffre et l'autre par un - , la chaîne commençant par - est le nombre le plus petit.
  • Si les deux chaînes commencent par un chiffre, comparez leur longueur. La chaîne la plus courte est le nombre le plus petit. Si les deux chaînes ont la même longueur, effectuez une comparaison de chaîne standard.
  • Si les deux chaînes commencent par - , comparez leur longueur. La plus longue chaîne est le plus petit nombre. Si les deux chaînes ont la même longueur, effectuez une comparaison de chaîne standard, mais annulez le résultat.
String str[]={"-123","89","-10","456"};

str est un tableau de chaînes, chaque chaîne ayant le format d'un entier et vous devez effectuer un tri sur ce tableau en un temps O(n log n) .

Les chaînes dans str peuvent représenter à la fois des entiers positifs et négatifs. La longueur maximale de ces chaînes est de 1024 caractères.

Je sais qu'une solution à ce problème consiste à convertir les chaînes en nombres, puis à les comparer en dehors de cela; Existe-t-il une autre solution à ce problème?


Voici un exemple minimal et potentiellement insuffisant (ne gère pas les zéros, les espaces, etc.) qui fait ce que vous voulez.

Les commentaires expliquent ce que ça fait. :)

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
  std::vector<std::string> strings = {
      "-1", "-1", "-20", "-4", "3", "0", "-0", "1", "20", "20", "44020",
  };

  // Assumes everything in "strings" has no whitespace in it.
  // Assumes everything in "strings" does not have leading zeroes.
  // Assumes everything in "strings" is an ascii representaion of an integer.
  // Assumes everything in "strings" is nonempty.
  std::sort(strings.begin(), strings.end(),
            [](const std::string &a, const std::string &b) {
              const bool a_is_negative = a[0] == '-';
              const bool b_is_negative = b[0] == '-';
              if (a_is_negative != b_is_negative) {
                // If they have different signs, then whichever is negative is
                // smaller.
                return a_is_negative;
              } else if (a.length() != b.length()) {
                // If they have the same sign, then whichever has more
                // characters is larger in magnitude. When the sign is negative,
                // the longer (more digits) number is "more negative". When
                // positive, the longer (more digits) number is "more positive".
                return (a.length() < b.length()) != a_is_negative;
              } else {
                // Otherwise a lexicographic comparison of "a" and "b" will
                // determine which string is larger in magnitude. Using the same
                // logic above, we account for the "negative vs. positive"
                // comparison.
                return (a < b) != a_is_negative;
              }
            });

  for (const auto &str : strings) {
    std::cout << str << " ";
  }
  std::cout << std::endl;
}




sorting