Largest Number (M)
题目
Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input: [10,2]
Output: "210"
Example 2:
Input: [3,30,34,5,9]
Output: "9534330"
Note: The result may be very large, so you need to return a string instead of an integer.
题意
给定一个数组，要求将其中所有数的顺序重新排列，使其能组成一个最大的数(字符串的形式)。
思路
对于整数a和b，如何确定哪个数放在前面，可以用如下方法：比较字符串ab和ba的字典序，若ab > ba则先放a，反之先放b。数组排好序后，将各元素依次拼接成字符串即为答案。如果排序后的数组第一个元素为0，说明后面所有元素都为0，只要返回0即可。
因为求的是最大数可以像上面这样简单处理，但如果求的是最小数则要进一步处理0的问题(因为0不能放在最大位上，这是无效的)，可以采取以下措施：1. 遍历一遍数组，统计0的个数为n，并将非零整数存入新数组中；2. 将新数组按照字典序进行排序；3. 在第一个元素后添加n个0。
代码实现
Java
class Solution {
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, new Cmp());
// 都一个元素为0，说明后面所有元素都为0
if (strs[0].equals("0")) {
return "0";
}
StringBuilder ans = new StringBuilder();
for (int i = 0; i < strs.length; i++) {
ans.append(strs[i]);
}
return ans.toString();
}
private class Cmp implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
return (o2 + o1).compareTo(o1 + o2);
}
}
}
JavaScript
/**
* @param {number[]} nums
* @return {string}
*/
var largestNumber = function (nums) {
nums.sort((a, b) => (a + '' + b <= b + '' + a ? 1 : -1))
if (nums[0] === 0) {
return '0'
}
return nums.join('')
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
