目錄
- 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;
}