Go&java算法之最大數(shù)示例詳解
最大數(shù)
給定一組非負整數(shù) nums，重新排列每個數(shù)的順序（每個數(shù)不可拆分）使之組成一個最大的整數(shù)。
注意：輸出結果可能非常大，所以你需要返回一個字符串而不是整數(shù)。
- 示例 1：
輸入：nums = [10,2]
輸出："210"
- 示例 2：
輸入：nums = [3,30,34,5,9]
輸出："9534330"
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 109
方法一：排序（java）
要想組成最大的整數(shù)，一種直觀的想法是把數(shù)值大的數(shù)放在高位。
于是我們可以比較輸入數(shù)組的每個元素的最高位，最高位相同的時候比較次高位
以此類推，完成排序，然后把它們拼接起來。這種排序方式對于輸入數(shù)組 沒有相同數(shù)字開頭 的時候是有效的
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
// 轉換成包裝類型，以便傳入 Comparator 對象（此處為 lambda 表達式）
Integer[] numsArr = new Integer[n];
for (int i = 0; i < n; i++) {
numsArr[i] = nums[i];
}
Arrays.sort(numsArr, (x, y) -> {
long sx = 10, sy = 10;
while (sx <= x) {
sx *= 10;
}
while (sy <= y) {
sy *= 10;
}
return (int) (-sy * x - y + sx * y + x);
});
if (numsArr[0] == 0) {
return "0";
}
StringBuilder ret = new StringBuilder();
for (int num : numsArr) {
ret.append(num);
}
return ret.toString();
}
}
時間復雜度：O(nlognlogm)
空間復雜度：O(logn)
方法一：排序（go）
具體的方法思路已經(jīng)在上文中表述，詳情請看上文內(nèi)容。
1.核心為插入排序
2.比大小的函數(shù)，相加的兩種string結果，然后比較各位大小。
3.將排序的結果累加
func largestNumber(nums []int) string {
sort.Slice(nums, func(i, j int) bool {
x, y := nums[i], nums[j]
sx, sy := 10, 10
for sx <= x {
sx *= 10
}
for sy <= y {
sy *= 10
}
return sy*x+y > sx*y+x
})
if nums[0] == 0 {
return "0"
}
ans := []byte{}
for _, x := range nums {
ans = append(ans, strconv.Itoa(x)...)
}
return string(ans)
}
時間復雜度：O(nlognlogm)
空間復雜度：O(logn)
以上就是Go&java算法之最大數(shù)示例詳解的詳細內(nèi)容，更多關于Go java算法最大數(shù)的資料請關注腳本之家其它相關文章！
相關文章
Java使用easyExcel導出excel數(shù)據(jù)案例
詳解Java編譯優(yōu)化之循環(huán)展開和粗化鎖
Spring Boot中使用activiti的方法教程（一）
Java GUI圖形界面開發(fā)實現(xiàn)小型計算器流程詳解
詳解在spring boot中配置多個DispatcherServlet
JDBC數(shù)據(jù)庫連接過程及驅動加載與設計模式詳解
IntelliJ IDEA基于Scala實現(xiàn)Git檢查工具