javascript - 排列:推送功能不起作用,JavaScript O(n*n!) 运行时
问题描述
手头的问题是:给定一个由不同整数组成的数组,返回所有可能的排列。您可以按任何顺序返回答案。
我的这段代码运行时间还可以,但推送功能似乎不起作用,我不确定为什么 bc 这一切都有意义
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.
var permute = function(nums) {
if (nums == null) {
return []
}
return getPermutations(nums);
};
function getPermutations(arr) {
var set = {}
var size = factorial(arr.length)
var result = []
while (Object.keys(set).length < size) {
for (var i = 0; i < arr.length && result.length < size; i++) {
for (var j = arr.length - 1; j >= 0 && result.length < size; j--) {
if (!set[arr]) {
set[arr] = 1
console.log(arr) //clearly see the permutations printed
result.push(arr) //why is this not working...
}
arr = swap(arr,i,j)
}
}
}
return result
}
function swap(arr,i,j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
return arr
}
function factorial(n) {
if (n == 0 || n == 1) {
return 1
}
return n*factorial(n-1)
}
解决方案
您将同一个数组多次推送到result
数组中。
arr
您可以通过在推送之前创建数组的副本来解决此问题。
(所以它之后的代码不能再次改变数组)
result.push(arr)
因此,您可以使用以下示例之一来代替:
// using splash operator
result.push([...arr]);
// Array#slice()
result.push(arr.slice());
// Array.from()
result.push(Array.from(arr));
// etc...
工作示例:
var permute = function(nums) {
if (nums == null) {
return []
}
return getPermutations(nums);
};
function getPermutations(arr) {
var set = {}
var size = factorial(arr.length)
var result = []
while (Object.keys(set).length < size) {
for (var i = 0; i < arr.length && result.length < size; i++) {
for (var j = arr.length - 1; j >= 0 && result.length < size; j--) {
if (!set[arr]) {
set[arr] = 1
console.log(arr) //clearly see the permutations printed
result.push([...arr]) //why is this not working...
}
arr = swap(arr,i,j)
}
}
}
return result
}
function swap(arr,i,j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
return arr
}
function factorial(n) {
if (n == 0 || n == 1) {
return 1
}
return n*factorial(n-1)
}
console.log(permute([1,2,3]));
这个问题也可能是一个很好的阅读,它包含了很多关于如何在 javascript 中有效地计算排列的例子。
推荐阅读
- node.js - 如何使用 Windows 身份验证设置 IIS/NGINX 反向代理(在 NodeJS 前面)
- c++ - 如何使用 cpp 程序读/写 EC(嵌入式控制器)寄存器
- sql - 有没有更好的方法来使用 Access SQL 执行多个 OR 条件 IIF 语句?
- javascript - 对部署在 Azure 的 Web 服务的 AJAX 调用不成功
- c# - 将非转义的 unicode 字符串转换为 unicode
- oracle - 是否可以使用 ALL_TABLES 查询表以获取计数 - ORACLE
- selenium - 如何为以下具有相同值的 img 类获取 xpath?
- android - Android:在 Google Play 游戏中获取用户名
- html - 如何强制 Flex Grid 宽度?
- algorithm - 奇怪的实验结果的原因是什么?