Почему моя программа не может сортировать целочисленные строки?

Question

Я пытался решить очень простой вопрос кодирования:

Рассмотрим массив числовых строк, где каждая строка представляет собой положительное число с числом от 1 до 10 ^ 6 цифр. Сортируйте элементы массива в неубывающем или возрастающем порядке их целочисленных значений и напечатайте каждый элемент отсортированного массива в новой строке.

Первая строка содержит целое число n, обозначающее количество строк. Каждая изВ следующих строках содержится INTEGER STRING.

Мой код:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int i; string s;
    cin >> i;
    int j = i;
    string arr[i];
    int cntr = 0;
    while (i--){
        cin >> s;
        arr[cntr] = s;
        cntr++;
    }
    sort(arr, arr+j);

    for (auto c: arr)
        cout << c << endl;

}

На входе

6
31415926535897932384626433832795
1
3
10
3
5

И мой вывод:

1
10
3
3
31415926535897932384626433832795
5

Если я создаю массив и добавляю в него целочисленные строки, приведенный выше код работает нормально. Тогда почему он дает неправильный результат, когда получает данные с веб-сайта?

PS: Вот ссылка на проблему: https://www.hackerrank.com/challenges/big-sorting/problem

Answer 1

Сначала используйте вектор строк вместо массива строк переменного размера (что недопустимо в C ++).

Функция сортировки STL использует лексикографический поиск для сортировки строк по умолчанию. Вам нужно передать свою собственную функцию сравнения, чтобы отсортировать целочисленные строки численно.

Предполагая, что целочисленные строки не имеют начальных 0;

sort(arr.begin(), arr.end(), [] (const string& s1, const string& s2) {
    return s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2);
});

Answer 2

Я дам вам альтернативное решение, так как C ++ уже отсортировал контейнеры.

Некоторые подсказки: пожалуйста, не используйте "using namespace std;"

C ++ не имел массивов переменной длины! Так что гораздо проще использовать тип контейнера! В этом примере мы используем std::multimap, который может сортировать элементы и разрешать дублирование.

#include <iostream>
#include <map>

// we want to use our own sorting algorithm for std::multimap
// this needs a functional object with operator() which do the compare
//
// works only for non negative numbers without leading '0's
struct compare
{
    bool operator()( const std::string& s1, const std::string& s2 ) const
    {
        // if the string contains a number as text, we can asume that
        // a number which has less characters is lesser
        if ( s1.size() < s2.size() ) return true;

        // if the size is bigger, the numerical value is bigger
        if ( s1.size() > s2.size() ) return false;

        // if both are equal length
        // so we simply compare lexigraphical
        // this works because a bigger diggit char always means a
        // bigger numerical value
        return s1 < s2;
    }
};

int main()
{
    // instead of later sort, we use a sorted container, multiset because we can use duplicates
    std::multiset<std::string, compare> data;

    // read data as in your code 
    int numberOfElementsToRead;
    std::string tmpInput;

    std::cin >> numberOfElementsToRead;

    while (numberOfElementsToRead--)
    {
        std::cin >> tmpInput;
        data.insert( tmpInput ); // insert automatically sorts
    }

    // print out the container
    for ( auto& s: data )
    {
        std::cout << s << std::endl;
    }
}

Answer 3

Это не сработает:

    int i;
    cin >> i;

    string arr[i];

Если вам нужно динамически изменить размер массива, используйте std :: vector (или new / delete, если вам действительно нужно).

    int i;
    cin >> i;

    std::vector<std::string> arr(i);

С точки зрения причин сбоя сортировки вы сортируете числа в алфавитном порядке, что означает, что все, что имеет «1» в начале, появится первым. Вместо этого сортируйте по числовому значению:

auto compareStringsNumerically = [](const std::string& a, const std::string& b) {
  return std::stoi(a) < std::stoi(b); //< compare integer values
};
std::sort(arr, arr + j, compareStringsNumerically);