179. Largest Number (Medium)

https://leetcode.com/problems/largest-number/

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"

Note: The result may be very large, so you need to return a string instead of an integer.

Solutions

class Solution {

    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }

        // 2276, 22
        // 2272, 227
        // 2273, 227

        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {

            // max common divisor
            private int getMCD(int m, int n) {
                if (m < n) {
                    int temp = m;
                    m = n;
                    n = temp;
                }

                while (m % n != 0) {
                    int temp = m % n;
                    m = n;
                    n = temp;
                }
                return n;
            }

            // least common multiple
            private int getLCM(int m, int n) {
                return m * n / getMCD(m, n);
            }

            @Override
            public int compare(Integer o1, Integer o2) {
                String str1 = o1 + "";
                String str2 = o2 + "";

                int len = getLCM(str1.length(), str2.length());
                // FIXME following condition statement is totally wrong
                // for (int i = 1; i < len / str1.length(); i++) {
                while (str1.length() < len) {
                    str1 += o1;
                }

                // for (int i = 1; i < len / str2.length(); i++) {
                while (str2.length() < len) {
                    str2 += o2;
                }

                for (int i = 0; i < len; i++) {
                    if (str1.charAt(i) > str2.charAt(i)) {
                        return -1;
                    }

                    if (str1.charAt(i) < str2.charAt(i)) {
                        return 1;
                    }
                }

                // the order doesn't matter if str1 == str2
                return 1;
            }
        });

        for (int i = 0; i < nums.length; i++) {
            queue.add(nums[i]);
        }

        String ans = "";
        while (!queue.isEmpty()) {
            ans += queue.poll();
        }

        // FIXME, following express will lead to overflow
        // remove invalid zeros, say "00", "000"
        // return Integer.valueOf(ans) + "";

        while (!ans.isEmpty() && ans.length() > 1) {
            if (ans.charAt(0) != '0') {
                break;
            }

            ans = ans.substring(1);
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""