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('')
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/128851.html
標籤：其他