JavaScript中sort方法的一个坑(leetcode 179. Largest Number)
在做 Largest Number 这道题之前,我对 sort 方法的用法是非常自信的。我很清楚不传比较因子的排序会根据元素字典序(字符串的UNICODE码位点)来排,如果要根据大小排序,需要传入一个比较函数。
先来看这道题,给你一个数组,让你把数组元素拼接起来,求能拼得的最大的数。如果只有两个数字 a 和 b,如何拼?很明显比较 ab 和 ba 两个数的大小,所以这道题首先需要对数组做一次排序。刷刷写下如下代码:
nums.sort(function(a, b) { return (b + '' + a) > (a + '' + b);});
因为 ba 和 ab 位数相同,我觉得根据字典序即可比较大小,提交,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]));
结果很明显:
最后勉强回忆起 C++ 中的 sort 的比较函数返回的是一个 bool 值,而 JavaScript 比较函数能返回三个值,跟 C++ 中的 qsort 类似?实在回忆不起来也不想回忆了。
本题完整代码可以移步 https://github.com/hanzichi/leetcode/tree/master/Algorithms/Largest%20Number。PS:还有一个坑,拼起来的字符串需要去前导 0。