LeetCode - Get Largest Number

發表於 更新於 分類於 閱讀次數： Disqus：

給予一個非負數的數字陣列，利用陣列內的元素排列出一個最大的數字，回傳值為字串

Test Case

這邊的解法直接丟上去 leetCode 還是會有問題，因為有些 testCase 沒覆蓋到，後續等有空時再繼續做…

Numbers Expected
[0, 0] 0
[10, 2] 210
[3, 30, 34, 5, 9] 9534330
[121, 12] 12121
[824, 938, 1399, 5607, 6973, 5703, 9609, 4398, 8247] 9609938824824769735703560743981399

解題方法很多，重點的比較規則是將兩個數字字串合併後，再去比較，c-sharp的部分利用string.Compare()比較字串避免溢位

Solution in Js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
  constructor() {}
  GetLargestNumber(numbers) {
    let sortList = numbers.sort(function(x, y) {
      let xFirst = x.toString() + y.toString();
      let yFirst = y.toString() + x.toString();
      return yFirst - xFirst;
    });
    let result = sortList.reduce((a, b) => {
      if (a == b) return a.toString();
      return a.toString() + b.toString();
    });
    return result;
  }
}

module.exports = Solution;

Solution in C-sharp

其實就直接將數字陣列利用 IComparer 實作比較的方法，一開始不需要弄成 Dictionary….
不過也懶得再重寫了，大概就是這個意思

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution20190510
{
    public string LargestNumber(int[] nums)
    {
        var myList = GetSortedList(nums);
        return GetLargestNumberByList(myList);
    }

    private string GetLargestNumberByList(IEnumerable<KeyValuePair<string, int>> myList)
    {
        var result = "";
        foreach (var keyValuePair in myList)
        {
            result += keyValuePair.Key;
        }
        return result;
    }

    private IEnumerable<KeyValuePair<string, int>> GetSortedList(IEnumerable<int> nums)
    {
        var dict = new Dictionary<string, int>();
        foreach (var num in nums)
        {
            if (dict.ContainsKey(num.ToString()))
            {
                continue;
            }
            dict.Add(num.ToString(), num);
        }
        var result = dict.ToList();
        result.Sort(mySort);

        return result;
    }

    private int mySort(KeyValuePair<string, int> x, KeyValuePair<string, int> y)
    {
        var xFirst = x.Key + y.Key;
        var yFirst = y.Key + x.Key;
        return string.Compare(yFirst, xFirst);
    }
}