LeetCode_排序_中等_179.最大數

目錄

• 1.題目
• 2.思路
• 3.代碼實作（Java）

1.題目

給定一組非負整數 nums，重新排列每個數的順序（每個數不可拆分）使之組成一個最大的整數。

注意：輸出結果可能非常大，是以你需要傳回一個字元串而不是整數。

示例 1：

輸入：nums = [10,2]

輸出：“210”

示例 2：

輸入：nums = [3,30,34,5,9]

輸出：“9534330”

示例 3：

輸入：nums = [1]

輸出：“1”

示例 4：

輸入：nums = [10]

輸出：“10”

提示：

1 <= nums.length <= 100

0 <= nums[i] <= 109

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/largest-number

2.思路

（1）利用簡單交換排序的思想對數組元素進行排序，不過排序的規則所有變化，先将要排序的兩個數nums[i]和nums[j]轉換為字元串a和b，然後用函數compareTo()比較a+b與b+a的大小，a+b==b+a傳回0，a+b>b+a傳回正數，a+b<b+a傳回負數。由于簡單交換排序的特點，即每完成一趟排序，就至少會有一個元素的位置确定，是以可以在排序的同時對結果進行字元串的拼接。

3.代碼實作（Java）

//（1）思路1
public String largestNumber(int[] nums) {
    int length=nums.length;
    if(length==1){
        return Integer.toString(nums[0]);
    }
    int tmp;
    String res="";
    for(int i=0;i<length;i++){
        for(int j=i+1;j<length;j++){
            String a=Integer.toString(nums[i]);
            String b=Integer.toString(nums[j]);
            if((a+b).compareTo(b+a)<0){
                tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }
        }
        //如果排序後的第一個元素是0，那其後面的元素肯定≤0，直接傳回0即可
        if(nums[0]==0) return "0";
        res+=Integer.toString(nums[i]);
    }
    return res;
}