题目描述(中等难度)
给一个数组,将这些数任意排列,组成一个值最大的数。
解法一
直觉上,我们应该先选最高位大的数。有 9
开头的数字先选 9
,然后选 8
开头的数,再选 7
开头的... 以此类推。所以我们需要一个函数来判断最高位是多少。
private int getHighestPosition(int num) { while (num / 10 > 0) { num /= 10; } return num; }
举个例子,比如对于 5,914,67
,先选 914
,再选 67
,再选 5
,组成 914675
,因为数字的高位越大越好,每次尽量选高位的大的数从而保证了最后构成的数一定是最大的。
接下来的一个问题,如果最高位的数字一样呢?又分成两种情况。
如果两个数字长度相等,比如 34
和 30
, 那么很明显,选择较大的即可。
如果两个数字长度不相等,比如 3
和 30
,此时先选择 3
还是先选择 30
呢?
我们只需要把它两拼接在一起直接去比较,也就是比较 330
和 303
,很明显是 330
大,所以我们先选择 3
。
所以我们可以封装一个比较函数。
private int compare(int n1, int n2) { int len1 = (n1 + "").length(); int len2 = (n2 + "").length(); //长度相等的情况 if (len1 == len2) { if (n1 > n2) { return 1; } else if (n1 < n2) { return -1; } else { return 0; } } //长度不等的情况 int combination1 = (int) (n1 * Math.pow(10, len2)) + n2; int combination2 =(int) (n2 * Math.pow(10, len1)) + n1; if (combination1 > combination2) { return 1; } else if (combination1 < combination2) { return -1; } else { return 0; } }
通过上边的分析,我们可以利用 HashMap
去存每一组数字,key
就是 9,8,7...0
分别代表开头数字是多少。而 value
就去存链表,每个链表的数字根据上边分析的规则将它们「从大到小」排列即可。
所以我们还需要一个插入元素到链表的方法。对于链表,我们的头结点不去存储值,而 head.next
才是我们第一个存储的值。
//将 node 通过插入排序的思想,找到第一个比他小的节点然后插入到它的前边 private void insert(MyNode head, MyNode node) { while (head != null && head.next != null) { int cur = head.next.val; int insert = node.val; if (compare(cur, insert) == -1) { node.next = head.next; head.next = node; return; } head = head.next; } head.next = node; }
然后对于 3,30,34,5,9
,我们就会有下边的结构。
9: head -> 9 8: 7: 6: 5: head -> 5 4: 3: head -> 34 -> 3 -> 30 2: 1: 0:
然后我们只需要依次遍历这些数字组成一个字符串即可,即9534330
。
然后把上边所有的代码合起来即可。
class MyNode { int val; MyNode next; MyNode(int val) { this.val = val; } } public String largestNumber(int[] nums) { HashMap<Integer, MyNode> map = new HashMap<>(); for (int i = 9; i >= 0; i--) { map.put(i, new MyNode(-1)); } //依次插入每一个数 for (int i = 0; i < nums.length; i++) { int key = getHighestPosition(nums[i]); //得到头指针 MyNode head = map.get(key); MyNode MyNode = new MyNode(nums[i]); //插入到当前链表的相应位置 insert(head, MyNode); } //遍历所有值 StringBuilder sb = new StringBuilder(); for (int i = 9; i >= 0; i--) { MyNode head = map.get(i).next; while (head != null) { sb.append(head.val); head = head.next; } } String res = sb.toString(); //考虑 "000" 只有 0 的特殊情况 return res.charAt(0) == '0' ? "0" : res; } private void insert(MyNode head, MyNode node) { while (head != null && head.next != null) { int cur = head.next.val; int insert = node.val; if (compare(cur, insert) == -1) { node.next = head.next; head.next = node; return; } head = head.next; } head.next = node; } private int compare(int n1, int n2) { int len1 = (n1 + "").length(); int len2 = (n2 + "").length(); if (len1 == len2) { if (n1 > n2) { return 1; } else if (n1 < n2) { return -1; } else { return 0; } } int combination1 = (int) (n1 * Math.pow(10, len2)) + n2; int combination2 = (int) (n2 * Math.pow(10, len1)) + n1; if (combination1 > combination2) { return 1; } else if (combination1 < combination2) { return -1; } else { return 0; } } private int getHighestPosition(int num) { while (num / 10 > 0) { num /= 10; } return num; }
解法二
仔细想一下上边的想法,我们通过每个数字的最高位人为的把所有数字分成 10
类,然后每一类做了一个插入排序。其实我们也可以不进行分类,直接对所有数字进行排序。
我们直接调用系统的排序方法,传一个我们自定义的比较器即可。看一下我们之前的比较函数是否可以用。
private int compare(int n1, int n2) { int len1 = (n1 + "").length(); int len2 = (n2 + "").length(); if (len1 == len2) { if (n1 > n2) { return 1; } else if (n1 < n2) { return -1; } else { return 0; } } int combination1 = (int) (n1 * Math.pow(10, len2)) + n2; int combination2 = (int) (n2 * Math.pow(10, len1)) + n1; if (combination1 > combination2) { return 1; } else if (combination1 < combination2) { return -1; } else { return 0; } }
之前我们只考虑了最高位相等的情况,如果最高位不同的话检查一下上边的代码是否还可以用。比如对于 93,234
,然后根据上边代码我们会比较 93234
和 23493
,然后我们会选择 93
,发现代码不需要修改。
此外,因为我们要从大到小排列,所以前一个数字大于后一个数字的时候,我们应该返回 -1
。
public String largestNumber(int[] nums) { //自带的比较器不能使用 int 类型,所以我们把它转为 Integer 类型 Integer[] n = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { n[i] = nums[i]; } Arrays.sort(n, new Comparator<Integer>() { @Override public int compare(Integer n1, Integer n2) { int len1 = (n1 + "").length(); int len2 = (n2 + "").length(); if (len1 == len2) { if (n1 > n2) { return -1; } else if (n1 < n2) { return 1; } else { return 0; } } int combination1 = (int) (n1 * Math.pow(10, len2)) + n2; int combination2 = (int) (n2 * Math.pow(10, len1)) + n1; if (combination1 > combination2) { return -1; } else if (combination1 < combination2) { return 1; } else { return 0; } } }); StringBuilder sb = new StringBuilder(); for (int i = 0; i < nums.length; i++) { sb.append(n[i]); } String res = sb.toString(); return res.charAt(0) == '0' ? "0" : res; }
分析一下时间复杂度,首先取决于我们使用的排序算法,如果是解法一的插入排序,那么就是 O(n²)
,如果是快速排序,那么就是 O(nlog(n)
,此外我们的比较函数因为要求出每个数字的长度,我们需要遍历一遍数字,记做 O(k)
,所以总的时间复杂度对于快排的话就是 O(nklon(n))
。
解法三
上边的解法严格来说其实还是有些问题的。在比较两个数字大小的时候,当长度不相等的时候,我们把两个数字合并起来。如果数字特别大,强行把它们合并起来是会溢出的。
所以我们可以把数字转为 String
,把字符串合并起来,然后对字符串进行比较。
此外,在比较函数中我们单独分别判断了数字长度相等和不相等的情况,其实长度相等的情况也是可以合并到长度不相等的情况中去的。
public String largestNumber(int[] nums) { Integer[] n = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { n[i] = nums[i]; } Arrays.sort(n, new Comparator<Integer>() { @Override public int compare(Integer n1, Integer n2) { String s1 = n1 + "" + n2; String s2 = n2 + "" + n1; //compareTo 方法 //如果参数是一个按字典顺序排列等于该字符串的字符串,则返回值为0; //如果参数是按字典顺序大于此字符串的字符串,则返回值小于0; //如果参数是按字典顺序小于此字符串的字符串,则返回值大于0。 return s2.compareTo(s1); } }); StringBuilder sb = new StringBuilder(); for (int i = 0; i < nums.length; i++) { sb.append(n[i]); } String res = sb.toString(); return res.charAt(0) == '0' ? "0" : res; }
总
只要找到了选取数字的原则,这道题也就转换成一道排序题了。