資訊專欄INFORMATION COLUMN
摘要：示例輸入輸出示例輸入輸出示例輸入輸出示例輸入輸出思路貪心給定一組非負(fù)數(shù)，重新排列使其組成一個(gè)最大的整數(shù)。具體過(guò)程如下自定義排序規(guī)則函數(shù)，將數(shù)組按照自定義排序規(guī)則重新排序。時(shí)間復(fù)雜度分析排序的時(shí)間復(fù)雜度為。
給定一組非負(fù)整數(shù) nums，重新排列每個(gè)數(shù)的順序（每個(gè)數(shù)不可拆分）使之組成一個(gè)最大的整數(shù)。
注意:
示例 1:
輸入：nums = [10,2]輸出："210"示例 2：
輸入：nums = [3,30,34,5,9]輸出："9534330"示例 3：
輸入：nums = [1]輸出："1"示例 4：
輸入：nums = [10]輸出："10"(貪心) O ( n l o g n ) O(nlogn) O(nlogn)
給定一組非負(fù)數(shù)，重新排列使其組成一個(gè)最大的整數(shù)。
樣例：
如樣例所示，[3,30,34,5,9]所能組成的最大數(shù)字是"9534330"，下面來(lái)講解貪心的做法。
假設(shè)給定我們包含兩個(gè)數(shù)字的數(shù)組[a,b]，如果"ab"組合大于"ba"組合，那么我們優(yōu)先選擇a進(jìn)行拼接。比如nums = [10,2]，"210"組合明顯大于"102"組合，因此我們優(yōu)先選擇2進(jìn)行拼接，這樣我們就自定義了一個(gè)排序規(guī)則。
但是擴(kuò)展到一個(gè)序列來(lái)講，一個(gè)序列要能夠正確地自定義排序，需要這種排序規(guī)則滿足全序關(guān)系，即以下三個(gè)關(guān)系：
a ≤ b 且 b ≤ a 則 a = b (反對(duì)稱性)a ≤ b 且 b ≤ c 則 a ≤ c (傳遞性)a ≤ b 或 b ≤ a (完全性)詳細(xì)證明可看官解。 滿足了全序關(guān)系，我們就可以將nums數(shù)組按照自定義排序規(guī)則重新排序，最后返回拼接好的字符串即可。
實(shí)現(xiàn)細(xì)節(jié)：
c++自定義排序，實(shí)現(xiàn)一個(gè)cmp函數(shù)。
static bool cmp(int a,int b) //自定義排序規(guī)則 { string as = to_string(a), bs = to_string(b); return as + bs > bs + as; }java自定義排序，Arrays.sort()結(jié)合lamda表達(dá)式。
Arrays.sort(s, (a, b) -> { String x = a + b, y = b + a ; return y.compareTo(x); }); 具體過(guò)程如下：
nums數(shù)組按照自定義排序規(guī)則重新排序。nums數(shù)組，取出nums中的每一個(gè)數(shù)，拼接到答案字符串res中。res是否是全0，如果是全0，則返回"0"，否則返回res。時(shí)間復(fù)雜度分析： 排序的時(shí)間復(fù)雜度 為 O ( n l o g n ) O(nlogn) O(nlogn) 。
class Solution {public: static bool cmp(int a,int b) //自定義排序規(guī)則 { 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; }};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) -> { //自定義排序規(guī)則 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. 最大數(shù)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/118800.html
摘要：找到給定的二維數(shù)組中最大的島嶼面積。思路給定一個(gè)由和組成的二維數(shù)組，其中代表島嶼土地，要求找出二維數(shù)組中最大的島嶼面積，沒有則返回。樣例如樣例所示，二維數(shù)組的最大島嶼面積為，下面來(lái)講解深度優(yōu)先搜索的做法。 ...
摘要：給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，今晚能夠偷竊到的最高金額。狀態(tài)表示表示偷竊號(hào)到號(hào)房間所能獲得的最高金額。下標(biāo)均從開始打家劫舍我們已經(jīng)知道了房間單排排列的狀態(tài)轉(zhuǎn)移方程，接下來(lái)思考房間環(huán)狀排列的做法。 ...
摘要：盡量減少操作次數(shù)。樣例如樣例所示，數(shù)組，移動(dòng)完成后變成，下面來(lái)講解雙指針的做法。這樣我們就完成了元素的移動(dòng)，同時(shí)也保持了非元素的相對(duì)順序。 目錄 1、題目2、思路...
摘要：第五題對(duì)稱二叉樹難度簡(jiǎn)單給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的。第十六題最大連續(xù)的個(gè)數(shù)難度簡(jiǎn)單給定一個(gè)二進(jìn)制數(shù)組，計(jì)算其中最大連續(xù)的個(gè)數(shù)。第十八題平方數(shù)之和難度簡(jiǎn)單給定一個(gè)非負(fù)整數(shù)，你要判斷是否存在兩個(gè)整數(shù)和，使得。 寫在前面 最近忙著調(diào)教新裝備，沒有及時(shí)的寫題解，但是沒有在偷懶沒刷題喔~來(lái)認(rèn)真整理下最近做的題目~ 之前考慮按tag來(lái)刷題，后來(lái)收到了推薦的leetcode題解，就根據(jù)上...
閱讀 2429·2021-11-24 10:31
閱讀 3487·2021-11-23 09:51
閱讀 2327·2021-11-15 18:11
閱讀 2450·2021-09-02 15:15
閱讀 2514·2019-08-29 17:02
閱讀 2346·2019-08-29 15:04
閱讀 908·2019-08-29 12:27
閱讀 2921·2019-08-28 18:15
