179 Largest Number
179. Largest Number
1. Question
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given[3, 30, 34, 5, 9]
, the largest formed number is9534330
.
Note: The result may be very large, so you need to return a string instead of an integer.
2. Implementation
(1) Sort
class Solution {
public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return "";
}
int n = nums.length;
String[] strs = new String[n];
for (int i = 0; i < n; i++) {
strs[i] = nums[i] + "";
}
Arrays.sort(strs, (a, b)->((b + a).compareTo(a + b)));
if (strs[0].charAt(0) == '0') {
return "0";
}
StringBuilder res = new StringBuilder();
for (String str : strs) {
res.append(str);
}
return res.toString();
}
}
3. Time & Space Complexity
时间复杂度O(nlogn), n是nums里的元素个数, 空间复杂度O(n)
Last updated
Was this helpful?