179. Largest Number

Question

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: "210"

Example 2:

Input: [3,30,34,5,9]
Output: "9534330"

Thinking:

• Method: Arrays.sort
  • 如果只有两个数[10, 2],只有两种可能210和102，我们知道210 > 102.
  • 我们通过comparator将数组中的所有元素进行排列，最后的结果依次append到一个StringBuilder中。

class Solution {
    public String largestNumber(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        int len = nums.length;
        String[] strs = new String[len];
        for(int i = 0; i < len; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                String cmp1 = s1 + s2;
                String cmp2 = s2 + s1;
                return cmp2.compareTo(cmp1);
            }
        });
        if(strs[0].startsWith("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i++)
            sb.append(strs[i]);
        return sb.toString();
    }
}

• Method 2: PriorityQueue,比Arrays.sort要快

class Solution {
    public String largestNumber(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        int len = nums.length;
        PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                String cmp1 = s1.concat(s2);
                String cmp2 = s2.concat(s1);
                return cmp2.compareTo(cmp1);
            }
        });
        for(int i= 0; i < len; i++)
            pq.add(String.valueOf(nums[i]));
        if(pq.peek().equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty())
            sb.append(pq.poll());
        return sb.toString();
    }
}

二刷

1. 使用PriorityQueue，其中使用Lambda表达式, 我发现Lambda表达式的速度慢。

   class Solution {
    public String largestNumber(int[] nums) {
        PriorityQueue<String> pq = new PriorityQueue<>((s1, s2) -> {
            return (-1) * (s1 + s2).compareTo(s2 + s1);
        });
        for(Integer num : nums) {
            pq.offer(num.toString());
        }
        if(pq.peek().equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty())
            sb.append(pq.poll());
        return sb.toString();
    }
   }
   

2. 使用匿名内部类速度快一些。

   class Solution {
    public String largestNumber(int[] nums) {
        PriorityQueue<String> pq = new PriorityQueue<>((s1, s2) -> {
            return (-1) * (s1 + s2).compareTo(s2 + s1);
        });
        for(Integer num : nums) {
            pq.offer(num.toString());
        }
        if(pq.peek().equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty())
            sb.append(pq.poll());
        return sb.toString();
    }
   }
   

3. 还想到一种方法，就是比较每一位数字，但是逻辑有缺陷，无法AC。

   class Solution {
    public String largestNumber(int[] nums) {
        PriorityQueue<String> pq = new PriorityQueue<>((s1, s2)->{
            int len1 = s1.length(), len2 = s2.length();
            int cur1 = 0, cur2 = 0, count = 0;
            while(count != 2){
                int c1 = s1.charAt(cur1++) - '0';
                int c2 = s2.charAt(cur2++) - '0';
                if(c1 > c2) return -1;
                else if(c2 > c1) return 1;
                if(cur1 == len1){
                    count++;
                    cur1 = 0;
                }
                if(cur2 == len2){
                    count++;
                    cur2 = 0;
                }
            }
            return 1;
        });
        for(int num : nums){
            pq.offer(Integer.toString(num));
        }
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty())
            sb.append(pq.poll());
        return sb.toString();
    }
   }
   

Reference

1. [LeetCode] 179. Largest Number Java