leetcode.179.最大数(largest-number)

我就是我 2022-11-18 05:52 105阅读 0赞

# 179.最大数 #

给定一组非负整数 `nums`，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

\*\*注意：\*\*输出结果可能非常大，所以你需要返回一个字符串而不是整数。

**示例 1：**

输入：nums = [10,2]
    输出："210"

**示例 2：**

输入：nums = [3,30,34,5,9]
    输出："9534330"

**示例 3：**

输入：nums = [1]
    输出："1"

**示例 4：**

输入：nums = [10]
    输出："10"

**提示：**

*  1 <= `nums.length` <=  100 100 100
 *  0 <= `nums[i]` <=  1 0 9 10^\{9\} 109

# 代码与思路 #

大概思路就是比较两个数，依次比较他们的最高位，如果最高位相同，比较次高位。（两个数位数不一样可以比较吗，也是可以的，比如\[45,123\]，4大于1，所以45放前面），这种排序对于输入数组**没有相同数字开头**的时候是有效的，比如`{ 45,56,81,76,123 };`得`81765645123`。  
输入数组**有相同数字开头**的情况：  
`[4,42]`比较，442>424，所以要把4放在前面;  
`[4,45]`比较，454>445，所以要把45放在前面。  
两个数字比较后，相对位置的关系就知道了，没有必要进行全排列比较。

#include <vector>
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <numeric>
    
    using namespace std;
    
    class Solution { 
    public:
    	string largestNumber(vector<int>& nums) { 
    		vector<string> vs;
    		transform(nums.begin(), nums.end(), back_inserter(vs), [](int x) { return to_string(x); });// algorithm---transform
    		sort(vs.begin(), vs.end(), [](const string& a, const string& b) { 
    			return a + b > b + a;
    			});
    		string res = accumulate(vs.begin(), vs.end(), string());// numeric---accumulate
    		return res[0] == '0' ? "0" : res;
    	}
    	string largestNumber2(vector<int>& nums) { 
    		// 将 nums 中的元素按照如下示例规则排序：
    		// 因 "2" + "10" > "10" + "2" , 故 2 排在 10 的前面 
    		sort(nums.begin(), nums.end(), [](int x, int y) { 
    			string a = to_string(x), b = to_string(y);
    			return a + b > b + a;
    		});
    		// 将排序后的数组转为字符串
    		string ans = "";
    		for (int n : nums) ans += to_string(n);
    		// 输入为 [0,0] 时，输出应该为 "0"
    		return ans[0] == '0' ? "0" : ans;
    	}
    };
    
    int main()
    { 
    	int nums[] = {  3,30,34,5,9 };
    	vector<int> v(nums, nums + 5);
    	for (auto it : v)
    	{ 
    		cout << it << endl;
    	}
    	Solution s;
    	cout << s.largestNumber(v) << endl;
    }

[参考][Link 1]

[Link 1]: https://leetcode-cn.com/problems/largest-number/solution/zui-da-shu-by-leetcode-solution-sid5/