179. Largest Number

179- Largest Number **Question Editorial Solution

Total Accepted: 50334 Total Submissions: 253493 Difficulty: Medium

Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9] , the largest formed number is 9534330 . Note: The result may be very large, so you need to return a string instead of an integer. **Credits:**Special thanks to @ts for adding this problem and creating all test cases.

Hide Tags Sort

 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
43
44
45
46
47
48
49
50
  /*The idea here is basically implement a String comparator to decide which String should come first during concatenation. Because when you have 2 numbers (let's convert them into String), you'll face only 2 cases:
        For example:
        
        String s1 = "9";
        String s2 = "31";
        
        String case1 =  s1 + s2; // 931
        String case2 = s2 + s1; // 319
        
        Apparently, case1 is greater than case2 in terms of value.
        So, we should always put s1 in front of s2.
        https://discuss.leetcode.com/topic/8018/my-java-solution-to-share
    */
    public String largestNumberJava7(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        String[] strArr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strArr[i] = String.valueOf(nums[i]);
        }
        // Comparator to decide which string should come first in concatenation
        Comparator<String> comp = new Comparator<String>(){
             @Override 
             public int compare(String str1, String str2) {
                 String s1 = str1 + str2;
                 String s2 = str2 + str1;
                 return s2.compareTo(s1); // reverse order here, so we can do append() later
             }
        };
        
        Arrays.sort(strArr, comp);
        
        // An extreme edge case by lc, say you have only a bunch of 0 in your int array
        if(strArr[0].charAt(0) == '0')
           return "0";
            
        
        StringBuilder sb = new StringBuilder();
        for (String str : strArr) {
            sb.append(str);
        }
        
        return sb.toString();
    }
    
    // https://discuss.leetcode.com/topic/7235/my-3-lines-code-in-java-and-python
    public String largestNumber(int[] num) {  // Thanks for Java 8, it makes code beautiful.
        String[] array = Arrays.stream(num).mapToObj(String::valueOf).toArray(String[]::new);
        Arrays.sort(array, (String s1, String s2) -> (s2 + s1).compareTo(s1 + s2));
        return Arrays.stream(array).reduce((x, y) -> x.equals("0") ? y : x + y).get();
    }

文章目录