Я написал код для этой проблемы:
Учитывая список неотрицательных целых чисел, расположите их так, чтобы они образовывали наибольшее число.
Например, учитывая [3, 30, 34, 5, 9], наибольшее сформированное число составляет 9534330.
Примечание. Результат может быть очень большим, поэтому вам нужно возвращать строку вместо целого числа.
Что я в основном пытаюсь добиться в этом коде, так это сначала использовать основную логику сортировки по старшей значащей цифре и расположить ее в порядке убывания. Позже я делаю для второй наиболее значимой цифры и так далее. я использовал std::sort()
Функция путем передачи вектора пар, где первая из пары является значением, а вторая из пары является индексом. Вот мой код:
bool radixOrder(pair<int,int> p1, pair<int,int> p2)
{
int val1=p1.first;
int e1=p1.second;
int val2=p2.first;
int e2=p2.second;
if(val1==val2 && e1==e2)
{
return val1==val2;
}
else if(((val1/e1)%10) == ((val2/e2)%10))
{
while(val1/e1 == val2/e2)
{
if(e1/10!=0)
e1=e1/10;
if(e2/10!=0)
e2=e2/10;
}
return (val1/e1)%10 > (val2/e2)%10;
}
else
{
return (val1/e1)%10 > (val2/e2)%10;
}
}
vector<pair<int,int> > createVNew(vector<int>& v)
{
vector<pair<int,int> > temp;
for(int i=0; i<v.size(); i++)
{
cout << i << endl;
int val=v[i], e=1;
if(v[i]==0)
{
temp.push_back(make_pair(val, 1));
}
else
{
while((e/v[i])==0)
e*=10;
if(e!=v[i])
{
temp.push_back(make_pair(val,e/10));
}
else if(e==v[i])
{
temp.push_back(make_pair(val,e));
}
}
}
return temp;
}
string largestNumber(vector<int>& v)
{
int e=1;
vector< pair<int,int> > vnew=createVNew(v);
sort(vnew.begin(), vnew.end(), radixOrder);
stringstream s;
for(int i=0; i<vnew.size(); i++)
{
s<<vnew[i].first;
}
return s.str();
}
largestNumber(..)
моя функция, которая возвращает желаемую строку. Теперь этот код работает нормально для большинства ненулевых входов, которые я мог бы попробовать. Но когда input представляет собой длинный вектор нулей, что-то вроде:
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 , 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 , 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 , 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ]
это дает исключение с плавающей запятой.
Я пытался найти решение, но не смог. Я новичок в cpp, и любая помощь будет отличной.
Ваш radixSort
функция нарушает Compare
требования, а именно нерефлексивность (то есть radixOrder(x, x)
должен вернуться false
но возвращается true
потому что исполнение идет к первому if
ветка).
Таким образом, вы получите классический пример неопределенного поведения здесь. Я считаю, что кусок кода должен быть переписан как-то
if (e1==e2)
{
return val1 > val2;
}
Хотя я бы решил проблему, просто отсортировав входные числа в виде строк в обратном порядке.