力扣题解(最大数)

发布于:2024-07-26 ⋅ 阅读:(114) ⋅ 点赞:(0)

排序179. 最大数

给定一组非负整数 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;

						}
};


网站公告

今日签到

点亮在社区的每一天
去签到