LeetCode 179. 最大数【c++/java详细题解】

tuantuan 发布于2021-09-02 15:15 / 2388人阅读

摘要：示例输入输出示例输入输出示例输入输出示例输入输出思路贪心给定一组非负数，重新排列使其组成一个最大的整数。具体过程如下自定义排序规则函数，将数组按照自定义排序规则重新排序。时间复杂度分析排序的时间复杂度为。

1、题目

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

注意:

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

示例 1:

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

示例 2：

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

示例 3：

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

示例 4：

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

2、思路

(贪心) $O (n l o g n)$

给定一组非负数，重新排列使其组成一个最大的整数。

样例：

如样例所示，[3,30,34,5,9]所能组成的最大数字是"9534330"，下面来讲解贪心的做法。

假设给定我们包含两个数字的数组[a,b]，如果"ab"组合大于"ba"组合，那么我们优先选择a进行拼接。比如nums = [10,2]，"210"组合明显大于"102"组合，因此我们优先选择2进行拼接，这样我们就自定义了一个排序规则。

但是扩展到一个序列来讲，一个序列要能够正确地自定义排序，需要这种排序规则满足全序关系，即以下三个关系：

如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)
如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)
如果 a ≤ b 或 b ≤ a (完全性)

详细证明可看官解。满足了全序关系，我们就可以将nums数组按照自定义排序规则重新排序，最后返回拼接好的字符串即可。

实现细节：

c++自定义排序，实现一个cmp函数。

static bool cmp(int a,int b) //自定义排序规则    {        string as = to_string(a), bs = to_string(b);        return as + bs > bs + as;    }

java自定义排序，Arrays.sort()结合lamda表达式。

Arrays.sort(s, (a, b) -> {            String x = a + b, y = b + a ;            return y.compareTo(x); });

具体过程如下：

1、自定义排序规则函数，将nums数组按照自定义排序规则重新排序。
2、从头到尾遍历nums数组，取出nums中的每一个数，拼接到答案字符串res中。
3、判断字符串res是否是全0，如果是全0，则返回"0"，否则返回res。

时间复杂度分析： 排序的时间复杂度为 $O (n l o g n)$ 。

3、c++代码

class Solution {public:    static bool cmp(int a,int b) //自定义排序规则    {        string as = to_string(a), bs = to_string(b);        return as + bs > bs + as;    }    string largestNumber(vector<int>& nums) {        sort(nums.begin(), nums.end(), cmp);        string res;        for(auto x : nums) res += to_string(x);        if(res[0] == "0") return "0"; //判断是否是全0        return res;    }};

4、java代码

class Solution {    public String largestNumber(int[] nums) {        int n = nums.length;        String[] s = new String[n];        for (int i = 0; i < n; i++) s[i] = nums[i] + "";        Arrays.sort(s, (a, b) -> {  //自定义排序规则            String x = a + b, y = b + a ;            return y.compareTo(x);        });            StringBuilder res = new StringBuilder();        for (String x : s) res.append(x);    	if(res.charAt(0) == "0") return "0"; //判断是否是全0        return res.toString();    }}

原题链接： 179. 最大数

GPU云服务器云服务器 java线程池最大线程数 cdn179 最大并发数最大连接数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/118800.html

LeetCode 695. 岛屿的最大面积【c++/java详细题解】

摘要：找到给定的二维数组中最大的岛屿面积。思路给定一个由和组成的二维数组，其中代表岛屿土地，要求找出二维数组中最大的岛屿面积，没有则返回。样例如样例所示，二维数组的最大岛屿面积为，下面来讲解深度优先搜索的做法。 ...

MangoGoing 2021-09-04 16:41 评论0 收藏0
LeetCode 213. 打家劫舍 II【c++/java详细题解】

摘要：给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。状态表示表示偷窃号到号房间所能获得的最高金额。下标均从开始打家劫舍我们已经知道了房间单排排列的状态转移方程，接下来思考房间环状排列的做法。 ...

Kyxy 2021-09-23 11:21 评论0 收藏0
LeetCode 283. 移动零【c++/java详细题解】

摘要：尽量减少操作次数。样例如样例所示，数组，移动完成后变成，下面来讲解双指针的做法。这样我们就完成了元素的移动，同时也保持了非元素的相对顺序。目录 1、题目2、思路...

cnsworder 2021-09-03 10:29 评论0 收藏0
小李飞刀：做题第十一弹！

摘要：第五题对称二叉树难度简单给定一个二叉树，检查它是否是镜像对称的。第十六题最大连续的个数难度简单给定一个二进制数组，计算其中最大连续的个数。第十八题平方数之和难度简单给定一个非负整数，你要判断是否存在两个整数和，使得。写在前面最近忙着调教新装备，没有及时的写题解，但是没有在偷懒没刷题喔~来认真整理下最近做的题目~ 之前考虑按tag来刷题，后来收到了推荐的leetcode题解，就根据上...

ytwman 2019-07-31 10:18 评论0 收藏0