Friday, April 24, 2015

[LeetCode] Largest Number

Largest Number

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.
Solution: Sorting! We need to implement the compare() function. A nice comparison can be done using strings, instead of integers. If we use integers, it would overflow. Special attention is also needed when we have at least two 0's in the array.
The following Java code has both selection sort and merge sort, while it only calls merge 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class Solution {
    public boolean compare(int a, int b) {
        return compare("" + a + b, "" + b + a);
    }
    
    public boolean compare(String s, String t) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < t.charAt(i)) {
                return false;
            } 
            if (s.charAt(i) > t.charAt(i)) {
                return true;
            }
        }
        return true;
    }
    
    public void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int max = nums[i];
            int idx = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (compare(nums[j], max)) {
                    max = nums[j];
                    idx = j;
                }
            }
            int tmp = nums[i];
            nums[i] = nums[idx];
            nums[idx] = tmp;
        }
    }
    
    public int[] mergeSort(int[] nums) {
        if (nums.length < 2) { 
            return nums;
        }
        
        int mid = (nums.length - 1) / 2;
        int[] left = mergeSort(
            Arrays.copyOfRange(nums, 0, mid + 1)
        );
        int[] right = mergeSort(
            Arrays.copyOfRange(nums, mid + 1, nums.length)
        );
        
        int i = 0;
        int j = 0;
        int k = 0;
        int[] arr = new int[nums.length];

        while (i < left.length && j < right.length) {
            if (compare(left[i], right[j])) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }
        
        while (i < left.length) {
            arr[k] = left[i];
            i++;
            k++;
        }
        while (j < right.length) {
            arr[k] = right[j];
            j++;
            k++;
        }
        
        return arr;
    }
    
    public String largestNumber(int[] nums) {
        nums = mergeSort(nums);
        String str = "";
        for (int num : nums) {
            str = str + num;
        }
        if (str.charAt(0) == '0') { 
            return "0";
        }
        return str;
    }
}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)