剑指offer - 把数组排成最小的数 - JavaScript
剑指offer - 把数组排成最小的数 - JavaScript
心谭博客
发布于 2020-04-21 15:39:50
发布于 2020-04-21 15:39:50
题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
方法 1: 暴力法
暴力法是通过回溯得到所有可能的排列结果，然后从其中挑选出最小的数字。
这种方法容易想到，虽然能得到正确结果，但是时间复杂度过高，会 TLE。
代码实现如下：
// 原文地址：https://xxoo521.com/2020-03-08-array-to-min-num/
/**
* @param {number[]} nums
* @return {string}
*/
var minNumber = function(nums) {
const result = [];
permutation(nums, 0, result);
result.sort((a, b) => {
if (a < b) return -1;
if (a > b) return 1;
return 0;
});
return result[0];
};
/**
* @param {number[]} nums
* @param {number} start
* @param {number[]} result
*/
function permutation(nums, start, result) {
if (start === nums.length) {
result.push(nums.join(""));
return;
}
for (let i = start; i < nums.length; ++i) {
[nums[i], nums[start]] = [nums[start], nums[i]];
permutation(nums, start + 1, result);
[nums[start], nums[i]] = [nums[i], nums[start]];
}
}方法 2: 快速排序
使用快速排序，可以将数字放在正确的位置上，从而满足题目的要求。例如对于数组【3，32】来说，它有两种排列方法：332、323。显然，323 符合题目的要求。那么在排序的过程中，就应该比较 332 和 323，然后返回正确的顺序。
在 js 中，可以通过参数将自定义的「排序依据」作为函数传入 sort 中，这个函数的逻辑是：
- 如果
a + b < b + a，说明 ab 比 ba 小，a 应该在 b 前面，返回-1 - 如果
a + b > b + a，说明 ab 比 ba 大，a 应该在 b 后面，返回 1 - 如果相等，返回 0
代码实现如下：
// ac地址：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
// 原文地址：https://xxoo521.com/2020-03-08-array-to-min-num/
/**
* @param {number[]} nums
* @return {string}
*/
var minNumber = function(nums) {
nums.sort((a, b) => {
const s1 = a + "" + b;
const s2 = b + "" + a;
if (s1 < s2) return -1;
if (s1 > s2) return 1;
return 0;
});
return nums.join("");
};时间复杂度是O(NlogN),空间复杂度是O(1)。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-03-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录