179. Largest Number

harry xie
2024-09-16 07:55:24

解題程式碼

var largestNumber = function (nums) {
  nums = nums.sort((a, b) => '' + a + '' + b > '' + b + '' + a ? -1 : 1);
  if (nums[0] === 0) return '0';
  return nums.join('');
};

解題思路演算法

一開始想到的是要讓陣列的值以字串的形式合併後要找到最大值，那肯定 9 開頭的數字要放在前面，而 1 開頭的數字放後面，將陣列依照上述邏輯做單純的降冪排列會發生一個問題，相同開頭的數字排序後，兩者合併得出的值不一定最大

ex: [ 927535, 92753, 9275, 927 ] 為排序後的陣列，92753927535 > 92753592753，故要想其他的邏輯去做排序，而這題可以將兩字串相加後去比大小做排序，s1+s2 > s2+s1

// [3,30,34,5,9] "9534 3 30"
// [3,35,34,5,9] "9535 34 3"
// [3,34,34,5,9] "9534 34 3"
// [3,32,34,5,9] "9534 3 32"

注意 edge case: [0, 0, 0, 0]，output 是 '0'

解法的時間空間複雜度

時間複雜度: O(n * log n)
空間複雜度: O(n)

參考資料

Largest Number - Leetcode 179 - Python