给定一组非负整数 nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
思路:
对数组重新排列,使得按照题目所要求的顺序输出。
排序规则:对于数组中的数a和数b,若ab>ba,则a在前,b在后。
正确性:若ab>ba,则acb>bca,保证了将任何数放ab之间,不改变大小关系。
因此按照上述做法得出的序列是x1,x2,x3.....,最优解是y1,y2,y3.....,假设前i-1个一样,则xi!=yi,假设xi==yj,则必有yiyj<yjyi,且对于处于i到j之间的数字组合z,yizyj<yjzyi,因此换i,j位置会大于等于未换位置的最优解,但是最优解是最大值,因此换后仍是最大值。因此贪心得到的是最优解。
class Solution {
public:
struct cmp2 {
void getarr(vector<int>& p, int a)
{
int i = 0;
while (a != 0)
{
int b = a % 10;
p.push_back(b);
a /= 10;
}
reverse(p.begin(), p.end());
}
bool operator () (int& p1, int& p2) //p1前,p2后
{
if(p1==p2)
return false;
if (p1 == 0)
return true;
else if (p2 == 0)
return false;
vector<int>q1;
vector<int>q2;
getarr(q2, p2);
getarr(q1, p1);
double tt=0;
for(int i=0;i<q1.size();i++)
{
tt=tt*10+q1[i];
}
for(int i=0;i<q2.size();i++)
{
tt=tt*10+q2[i];
}
double tt2=0;
for(int i=0;i<q2.size();i++)
{
tt2=tt2*10+q2[i];
}
for(int i=0;i<q1.size();i++)
{
tt2=tt2*10+q1[i];
}
return tt2>tt;
};
};
string largestNumber(vector<int>& nums) {
priority_queue<int, vector<int>, cmp2>dp;
int flag=0;
for (auto e : nums)
{
dp.push(e);
if(e!=0)
flag=1;
}
string ret;
if(flag==0)
return "0";
for (int i = 0; i < nums.size(); i++)
{
int a = dp.top();
dp.pop();
ret += to_string(a);
}
return ret;
}
};