LeetCode 179. 最大数
原题链接
中等
作者:
bruce
,
2021-01-09 11:57:31
,
所有人可见
,
阅读 299
#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
/**
* 179 找到数组中数字元素组合的最大数字
* 比如:
* given [3, 30, 34, 5, 9], the largest formed number is 9534330
*/
/**
* 方法 1,定义一个新的排序操作,
* 就是a<=b等价于ab <= ba;
* a==b 等价于 ab == ba;
* 当时这种新的比较符号是不是可以进行比较呢?
* 比如:
* a<b; b<c; c<a;
* 不满足这个比较定义;
* 所以需要证明一下新的比较运算是不是满足全序关系,参考链接如下
* https://baike.baidu.com/item/%E5%85%A8%E5%BA%8F%E5%85%B3%E7%B3%BB/943310?fromtitle=%E5%85%A8%E5%BA%8F&fromid=10577699
* 简单来说就是满足一下三个关系:
* 如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)
* 如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)
* 如果 a ≤ b 或 b ≤ a (完全性)
*/
static bool compare(int a, int b)
{
auto stra = to_string(a);
auto strb = to_string(b);
return (stra + strb > strb + stra); //小于号就是返回最小数。
}
string largestNumber1(vector<int> &nums)
{
sort(nums.begin(), nums.end(), compare);
string res;
for (auto i : nums)
{
res += to_string(i);
}
//以下两句是说去掉最小数的时候0打头的情况,一般最大数的同时为0的情况也需要判断
auto pos = res.find_first_not_of('0'); // 找到第一个不是0的位置
return pos == string::npos ? "0" : res.substr(pos); // 如果全是0,返回“0”;否则 return res;
// 在求最大的数的时候没有问题,但是如果是最小数的话那么可能有0打头。
}
/**
* 方法 2,思路和方法 1一样,但是写法不同
*/
string largestNumber2(vector<int> &nums)
{
sort(nums.begin(), nums.end(), [](int x, int y) {
string a = to_string(x), b = to_string(y);
return a + b > b + a;
});
string res;
for (auto x : nums)
res += to_string(x);
int k = 0;
while (k + 1 < nums.size() && res[k] == '0')
k++;
return res.substr(k);
}