求数组中所有数字可拼出的最大整数

遇到这样一个题:实现一个函数,求数组中所有数字可拼出的最大整数。举例:

maxNum([0, 4, 19, 41, 70]) // 70441190
maxNum([3, 30, 34, 5, 9]) // 9534330
maxNum([539, 53]) // 53953
maxNum([]) // 0

这个题目实际上是对数组进行排序,排序的规则是让最大的数字排在高位,比如:70和41比较,7大于4,所以70应该放在41前;但是有特殊情况,如果两个数字前几位都相同该怎么办,比如539和53,5和3都相同,此时应该用539中的9和53的第一位5比较,9大于5,所以539应该放在前面。

实现的步骤为:

  1. 将数字转为字符串,依次比较两个数字的每一位,将高位更大的数字排在前面;
  2. 如果两个数字 a, b 的长度分别为 n 和 n+m,且前 n 位都相同,那么用 a[0] 和 b[n] 进行比较;

代码如下:

function maxNum(arr) {
  function sortFn(num1, num2) {
    num1 = `${num1}`;
    num2 = `${num2}`;
    let num1Len = num1.length;
    let num2Len = num2.length;
    let num1Index = 0;
    let num2Index = 0;

    while (1) {
      if (num1[num1Index] === num2[num2Index]) {
        num1Index++;
        num2Index++;
        // num1已遍历结束,num2未结束
        if (num1Index === num1Len && num2Index < num2Len) {
          return +num2[num2Index] - (+num1[0]);
        }
        // num2已遍历结束,num1未结束
        if (num2Index === num2Len && num1Index < num1Len) {
          return +num2[0] - (+num1[num1Index]);
        }
        // num1和num2都已遍历结束
        if (num1Index === num2Len && num2Index === num2Len) {
          return +num2[num2Index] - (+num1[num1Index]);
        }
      } else {
        return +num2[num2Index] - (+num1[num1Index]);
      }
    }
  }
  return +arr.sort(sortFn).join('');
}

你可能感兴趣的