Kristian Kamenov Kristian Kamenov - 9 days ago 6
C++ Question

Get Median Element Of Vector Of Strings [C++]

I have the following task:
Given a set of N positive numbers. Write a program which finds the middle element of the set.
Input: on the first line there are number of examples,
the second line is for the length of the set. The next line is for the numbers of the set separated with space.
Something line this:

2 (number of examples)

5 (length)

12 4 22 31 32 (set)

8 (length)

22 33 44 11 55 66 88 99 (set)


Then you have to sort the set and print the middle element.
Output:

22 (mid elem of first set)

44 (mid elem of second set)


Constraints: N < 10^11 and each number of set should be < 10^20

So i choose to work directly with strings because of the big numbers. Here is my code:


#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;
}


And after compiling it stop on the second row for inputing the length of the first example and i got the error of type 0xC00000005. Any help would be appreciated.

Answer

The biggest issue with your code that I can see is that using atoi in the comparator is not going to work. If the input data is bigger than what and int can hold then atoi will not work as it tries to convert the string to an int.

What you can do though is compare the strings to each other. You have to take the sized into account otherwise 100 would come before 5 but it is not hard to implement. Something like the following should work.

bool comparer (const string& s1, const string& s2)
{
    if (s1.size() != s2.size())
        return s1.size() < s2.size();
    return s1 < s2;
}

Note that I changed s1 and s2 to be references as passing by value will create a lot of copies and kill the performance.