c++ - 获取字符串 vector 的中值元素 [C++]

Question

我有以下任务:给定一组 N 个正数。编写一个程序，找出集合的中间元素。输入:第一行有一些例子，第二行是集合的长度。下一行是用空格分隔的集合的数字。这条线的东西:
2(例子数)
5(长度)
12 4 22 31 32 (组)
8(长度)
22 33 44 11 55 66 88 99(组)

然后你必须对集合进行排序并打印中间元素。输出:
22(第一组中段)
44(第二组中段)

约束条件:N < 10^11 且每个组数应< 10^20
由于数字很大，所以我选择直接使用字符串。这是我的代码:

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;

bool comparer (const string s1, const string s2)
{
   return atoi(s1.c_str()) < atoi(s2.c_str());
}


int main()
{
    int numberOfExamples;
    cin >> numberOfExamples;

    for (int i = 0; i < numberOfExamples; i++)
    {
        long length;
        string input;
        cin >> length;
        string buffer;
        while(getline(cin, input))
        {
            vector<string> v;
            istringstream is(input);
            while (is >> buffer) v.push_back(buffer);

            sort (v.begin(), v.end(), comparer);

            string middle;
            if (v.size() % 2 == 0)
            {
                middle = v[v.size()/2 -1];
            }
            else
            {
                middle = v[v.size()/2];
            }
            cout << middle;
        }

    }
    return 0;
}

编译后它停在第二行以输入第一个示例的长度，我得到类型为 0xC00000005 的错误。任何帮助将不胜感激。

Answer 1

您要实现的算法是:

• 阅读测试数量； 忽略该行的其余部分。
• 对于每个测试
  • 读取测试值的数量，忽略该行的其余部分
  • 读取包含测试值的单行
  • 将测试线拆分为值 vector
  • 排序 vector
  • 找到中间元素

上面的粗体部分您要么失败了，要么就是根本没有做。例如，您的代码:

cin >> length; 
string buffer;
while(getline(cin, input))

将以整数形式读取格式化长度，但当前行的其余部分(可能只是一个换行符)留在输入流中。因此 getline 使用 that，而不是测试值行。更糟糕的是，这意味着 for 循环内的所有逻辑都将使用空输入行，这意味着 vector 中不会存储任何值。这意味着当你到达这里时:

if (v.size() % 2 == 0)
{
    middle = v[v.size()/2 -1];
}

v.size() 为零，这意味着 v.size() % 2 为零，这意味着您的“中间”现在设置为 v[-1]，明显越界。

所以最大的问题是您没有正确使用格式化输入后剩余的行数据，这是 C++ 初学者的常见问题。 See this question and related answers .

第二个问题，while (getline(...)) 是错误的。这将消耗所有数据，直到文件末尾。您只需要一行数据；不是所有剩余的数据行。一旦解决了前面提到的格式化输入问题，while 应该改为 if。

代码

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <string>
#include <limits>
#include <iterator>

int main()
{
    unsigned int numberOfExamples;
    if (!(std::cin >> numberOfExamples) || numberOfExamples == 0)
        return EXIT_FAILURE;

    while (numberOfExamples-- > 0)
    {
        unsigned int n_tests = 0;
        if (std::cin >> n_tests)
        {
            if (n_tests == 0)
                continue;

            // consume remainder of test lines
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

            // read set of values
            std::string line;
            if (std::getline(std::cin, line))
            {
                std::istringstream iss(line);
                std::vector<int> v {
                    std::istream_iterator<int>(iss),
                    std::istream_iterator<int>() };

                if (v.size() > 0)
                {
                    std::sort(v.begin(), v.end());

                    if (v.size() % 2 == 0)
                        std::cout << v[v.size()/2-1] << '\n';

                    else
                        std::cout << v[v.size()/2] << '\n';
                }
            }
        }
        else
        {
            std::cerr << "Failed to read number of test values\n";
        }
    }
}

输入

2
5
12 4 22 31 32
8
22 33 44 11 55 66 88 99

输出

22
44

See it live