299. Sort Decimal Real Number Strings

Sort Decimal Real Number Strings

Given a list of strings representing positive, negative, or decimal real numbers, sort the strings in ascending numerical order without converting their numerical values to any arithmetic data type.

Return the original string representations. If multiple strings represent the same numerical value, preserve their order from the input list.

Number Format

A number may begin with an optional - sign.
It contains one or more digits before an optional decimal point.
If a decimal point is present, at least one digit follows it.
Leading and trailing zeroes are allowed.
Different strings such as "2", "02.0", and "2.000" may represent the same numerical value.
Zero representations such as "0", "-0", "0.000", and "-000.0" are numerically equal.
The input will not contain numbers written in scientific notation, such as "1e-4", "2E3", or "-5.2e10".
The input will not contain numbers with a leading + sign.

Method Signature

List<String> sortRealNumbers(List<String> numbers)

numbers contains the real numbers as strings.
Return a new list containing the original strings in ascending numerical order.
Do not modify the input list numbers.
Numerically equal strings must remain in the same relative order as in numbers.
Do not parse the numerical value of an input string, or its integer or fractional parts, into an integer, floating-point, decimal, big-number, or other arithmetic data type.
Numerical comparisons must be performed using string operations. Integer indices, lengths, and counters may still be used.

Constraints

1 <= numbers.size() <= 100,000
1 <= numbers.get(i).length() <= 10,000
The total number of characters across all strings does not exceed 500,000.
Every string follows the number format described above.
No input string is empty.
Scientific notation such as "1e-4" will not appear in the input.

Examples

Example 1

sortRealNumbers(numbers = List.of("14.25", "-3.8", "0", "7.01", "-12"))

Output: List.of("-12", "-3.8", "0", "7.01", "14.25")

Example 2

sortRealNumbers(numbers = List.of("5.40", "005.4", "-0.25", "18", "5.4000", "0.003"))

Output: List.of("-0.25", "0.003", "5.40", "005.4", "5.4000", "18")

The strings "5.40", "005.4", and "5.4000" have the same numerical value, so their original relative order is preserved.

Example 3

sortRealNumbers(numbers = List.of("-0002.50", "-11.7", "100000000000000000000.1", "99.99"))

Output: List.of("-11.7", "-0002.50", "99.99", "100000000000000000000.1")

Example 4

sortRealNumbers(numbers = List.of("-0", "0.000", "-0.10", "-000.0", "0", "0.01"))

Output: List.of("-0.10", "-0", "0.000", "-000.0", "0", "0.01")

The strings "-0", "0.000", "-000.0", and "0" all represent zero, so their original relative order is preserved.