JAVA solution using radix sort


  • 0
    W
    public String largestNumber(int[] nums) {
        int n = nums.length;
        int[] leng = new int[n];
        int maxLen = 0;
        String[] numStr = new String[n];
        for(int i = 0; i < n; i ++) {
            numStr[i] = Integer.toString(nums[i]);
            leng[i] = numStr[i].length();
            if (leng[i] > maxLen) maxLen = leng[i];
        }
        for(int k = maxLen; k >=0; k --) {
            String[] tmpStr = new String[n];
            int[] count = new int[10];
            Arrays.fill(count,0);
            for(int i = 0; i < n; i ++) {
                int digit = numStr[i].charAt(k % numStr[i].length()) - '0';
                count[digit] ++;
            }
            for(int j = 1; j < 10; j ++) {
                count[j] = count[j] + count[j - 1];
            }
            for(int i = n - 1; i >=0; i --) {
                int digit = numStr[i].charAt(k % numStr[i].length()) - '0';
                tmpStr[count[digit] - 1] = numStr[i];
                count[digit] --;
            }
            for(int i = 0; i < n; i ++) {
                numStr[i] = tmpStr[i];
            }
        }
        if (n == 0 || numStr[n-1].equals("0"))
            return "0";
        StringBuffer strbuf = new StringBuffer();
        for(int i = n-1; i >= 0;i --) {
            strbuf.append(numStr[i]);
        }
        return strbuf.toString();
    }

  • 0
    S

    For [112,1121121], your solution will give a wrong answer. Actually, if the input include something like s1 and s2 is the prefix of n*s1, you solution might be incorrect because failing to consider the following digit implying by the shorter one.


  • 0
    S

    And one way to avoid it is to compare (MaxLength2-1) bits. If there need a change of position which is correct. One the other way, if there is no need to change the position, it means for S1 the MaxLength2-1 bits is the same as S2. And since the #bits we get after combination of them is less or equal to MaxLength*2-1, the combination will be the same value regardless of the order of S1and S2


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.