179.最大数

链接：179.最大数
难度：Medium
标签：贪心、数组、字符串、排序
简介：给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

题解 1 - javascript

• 编辑时间：2020-04-22
• 执行用时：116ms
• 内存消耗：36.4MB
• 编程语言：javascript
• 解法介绍：定义排序规则，先判断最大位，位数不相同又一次判断。

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function (nums) {
  let spliltNums = [];
  for (const num of nums) {
    spliltNums.push(numSpilt(num));
  }
  spliltNums = spliltNums.sort(sortFn);
  return arrJoin(spliltNums);
};
function numSpilt(num) {
  if (num === 0) {
    return [0];
  }
  const splitArr = [];
  while (num !== 0) {
    splitArr.push(num % 10);
    num = Math.floor(num / 10);
  }
  return splitArr.reverse();
}
function arrJoin(arr) {
  let res = arr.map(value => value.join('')).join('');
  while (res[0] === '0' && res.length !== 1) {
    res = res.substr(1);
  }
  return res;
}
function sortFn(num1, num2) {
  const len1 = num1.length;
  const len2 = num2.length;
  let minLen = Math.min(len1, len2);
  for (let i = 0; i < minLen; i++) {
    if (num2[i] !== num1[i]) {
      return num2[i] - num1[i];
    }
  }
  if (len1 === len2) return 0;
  if (minLen === len1) {
    const lNum = num2[minLen];
    for (let i = 0; i < minLen; i++) {
      const comp = num2[i];
      if (lNum !== comp) return lNum - comp;
    }
    const llNum = num2[minLen + 1];
    if (num2[minLen + 1] !== lNum) {
      return llNum - lNum;
    }
    return -1;
  } else {
    const lNum = num1[minLen];
    for (let i = 0; i < minLen; i++) {
      const comp = num1[i];
      if (lNum !== comp) return comp - lNum;
    }
    const llNum = num1[minLen + 1];
    if (num1[minLen + 1] !== lNum) {
      return lNum - llNum;
    }
    return 1;
  }
}

题解 2 - typescript

• 编辑时间：2021-04-12
• 执行用时：96ms
• 内存消耗：39.2MB
• 编程语言：typescript
• 解法介绍：合并两个字符串进行比较。

function largestNumber(nums: number[]): string {
  const getCount = (num: number): number => {
    if (num === 0) return 1;
    let c = 0;
    while (num) {
      num = ~~(num / 10);
      cpp;
    }
    return c;
  };
  nums.sort((num1, num2) => {
    const count1 = getCount(num1);
    const count2 = getCount(num2);
    const left = num1 * 10 ** count2 + num2;
    const right = num2 * 10 ** count1 + num1;
    return right - left;
  });
  return nums[0] === 0 ? '0' : nums.join('');
}