JavaScript中sort方法的一个坑(leetcode 179. Largest Number)

时间:2022-09-27 22:24:09

在做 Largest Number 这道题之前,我对 sort 方法的用法是非常自信的。我很清楚不传比较因子的排序会根据元素字典序(字符串的UNICODE码位点)来排,如果要根据大小排序,需要传入一个比较函数。

先来看这道题,给你一个数组,让你把数组元素拼接起来,求能拼得的最大的数。如果只有两个数字 a 和 b,如何拼?很明显比较 abba 两个数的大小,所以这道题首先需要对数组做一次排序。刷刷写下如下代码:

nums.sort(function(a, b) {
  return (b + '' + a) > (a + '' + b);
});

因为 baab 位数相同,我觉得根据字典序即可比较大小,提交,221 组数据跪在了 201 组。我开始怀疑算法的正确性,直到无意中把比较函数改了下,便 AC 了:

nums.sort(function(a, b) {
  return (b + '' + a) - (a + '' + b);
});

这真的有区别么?印象中 c++ 中调用 STL 的 sort 函数,在比较函数中一直用的 < 以及 > 啊。我承认我以前从没有留意过。

我们把问题简化,先来看以下代码:

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    return a - b;
  });

  return nums;
};

console.log(largestNumber([41,32,81,97,99,91,90,63,76,76,67]));
// [32, 41, 63, 67, 76, 76, 81, 90, 91, 97, 99]

这是一次升序排序,结果完美,那么,为什么能得到这样的结果,有思考过 return a - b 的意思么?

如果指明了 compareFunction ,那么数组会按照调用该函数的返回值排序。记 a 和 b 是两个将要被比较的元素:

  • 如果 compareFunction(a, b) 小于 0 ,那么 a 会被排列到 b 之前;
  • 如果 compareFunction(a, b) 等于 0 , a 和 b 的相对位置不变。
  • 如果 compareFunction(a, b) 大于 0 , b 会被排列到 a 之前。

上面的的代码其实可以扩写成这样:

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    if (a - b > 0)
      return 1; // a 比 b 大,b 排到 a 前
    else if (a - b < 0)
      return -1;  // a 比 b 小,a 排到 b 前
    else
      return 0; // a 和 b 一样大,a 和 b 相对位置不变
  });

  return nums;
};

仔细想想,这样便是一个升序排列。

再来看错误写法:

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    return a > b;
  });

  return nums;
};

console.log(largestNumber([41,32,81,97,99,91,90,63,76,76,67]));
// [91, 41, 32, 63, 67, 76, 76, 81, 90, 97, 99]

其实可以扩写为:

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    if (a > b)
      return 1; // true 隐式转换为 1; b 排到 a 前
    else
      return 0; // false 隐式转换为 0; 相对位置不变
  });

  return nums;
};

仔细想想,明显有问题。a > b 时 b 排到 a 前没有问题,a < b 时位置不变,这就不对了。如果 a < b 时 return -1,让 a 排到 b 前,就对了。所以这样写也是没问题的:

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    if (a > b)
      return 1;
    else
      return -1;
  });

  return nums;
};

当然,a === b 这个条件可以随意归到 a > b 或者 a < b 那,也可以拎出来独立,以上代码我是归到 a < b 那了。

另外还需要注意的一点是,比较函数中的 a 和 b 参数,在数组中的位置是任意的,并不是 a 前 b 后。这里我写了段测试代码:

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    console.log(a, b);
    console.log(nums.concat());
    return a - b;
  });

  return nums;
};

console.log(largestNumber([41,32,81,97,99,91,90,63,76,76,67]));

结果很明显:

JavaScript中sort方法的一个坑(leetcode 179. Largest Number)

最后勉强回忆起 C++ 中的 sort 的比较函数返回的是一个 bool 值,而 JavaScript 比较函数能返回三个值,跟 C++ 中的 qsort 类似?实在回忆不起来也不想回忆了。

本题完整代码可以移步 https://github.com/hanzichi/leetcode/tree/master/Algorithms/Largest%20Number。PS:还有一个坑,拼起来的字符串需要去前导 0。