目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給定一組非負整數 nums，重新排列每個數的順序（每個數不可拆分）使之組成一個最大的整數，
注意:
- 輸出結果可能非常大，所以你需要回傳一個字串而不是整數，
示例 1:
輸入：nums = [10,2]
輸出："210"
示例 2：
輸入：nums = [3,30,34,5,9]
輸出："9534330"
示例 3：
輸入：nums = [1]
輸出："1"
示例 4：
輸入：nums = [10]
輸出："10"
2、思路
(貪心) O ( n l o g n ) O(nlogn) O(nlogn)
給定一組非負數，重新排列使其組成一個最大的整數，
樣例：
如樣例所示，[3,30,34,5,9]所能組成的最大數字是"9534330"，下面來講解貪心的做法，
假設給定我們包含兩個數字的陣列[a,b]，如果"ab"組合大于"ba"組合，那么我們優先選擇a進行拼接，比如nums = [10,2]，"210"組合明顯大于"102"組合，因此我們優先選擇2進行拼接，這樣我們就自定義了一個排序規則，
但是擴展到一個序列來講，一個序列要能夠正確地自定義排序，需要這種排序規則滿足全序關系，即以下三個關系：
- 如果
a ≤ b且b ≤ a則a = b(反對稱性) - 如果
a ≤ b且b ≤ c則a ≤ c(傳遞性) - 如果
a ≤ b或b ≤ a(完全性)
詳細證明可看官解， 滿足了全序關系，我們就可以將nums陣列按照自定義排序規則重新排序，最后回傳拼接好的字串即可，
實作細節：
c++自定義排序，實作一個cmp函式，
static bool cmp(int a,int b) //自定義排序規則
{
string as = to_string(a), bs = to_string(b);
return as + bs > bs + as;
}
java自定義排序，Arrays.sort()結合lamda運算式，
Arrays.sort(s, (a, b) -> {
String x = a + b, y = b + a ;
return y.compareTo(x);
});
具體程序如下：
- 1、自定義排序規則函式，將
nums陣列按照自定義排序規則重新排序， - 2、從頭到尾遍歷
nums陣列，取出nums中的每一個數，拼接到答案字串res中， - 3、判斷字串
res是否是全0，如果是全0，則回傳"0"，否則回傳res，
時間復雜度分析： 排序的時間復雜度 為 O ( n l o g n ) O(nlogn) O(nlogn) ，
3、c++代碼
class Solution {
public:
static bool cmp(int a,int b) //自定義排序規則
{
string as = to_string(a), bs = to_string(b);
return as + bs > bs + as;
}
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), cmp);
string res;
for(auto x : nums) res += to_string(x);
if(res[0] == '0') return "0"; //判斷是否是全0
return res;
}
};
4、java代碼
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
String[] s = new String[n];
for (int i = 0; i < n; i++) s[i] = nums[i] + "";
Arrays.sort(s, (a, b) -> { //自定義排序規則
String x = a + b, y = b + a ;
return y.compareTo(x);
});
StringBuilder res = new StringBuilder();
for (String x : s) res.append(x);
if(res.charAt(0) == '0') return "0"; //判斷是否是全0
return res.toString();
}
}
原題鏈接： 179. 最大數
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/296868.html
標籤：java
上一篇：2021Java開發工程師必備知識，Java后端學習主流知識學習系列（一）（建議先收藏）
下一篇：JAVA結構化編程