在代码战训练中，我遇到了一个关于约瑟夫排列的挑战，我试着先在纸上解决它，然后将其翻译成代码。
问题如下:“创建一个返回约瑟夫斯排列的函数，将要排列的项目的初始数组/列表作为参数，就像它们在一个圆中一样，每k个位置计数一次，直到没有剩余为止。”
我的主要想法是：
>
使用两个迭代器：
将I初始化为0，将k初始化为1
function josephus(items,step){
var output = [];
var i = 0;
var k = 1;
if( items == [] ) {
return [];
}
while (items.length != 1) {
if (k == step && i == items.length - 1) {
output.push(items[i]);
items.splice(i, 1);
i = 0;
k = 1;
} else if (k == step && i != items.length - 1) {
output.push(items[i]);
items.splice(i, 1);
k = 1
} else if (k < step && i == items.length - 1) {
k++;
i=0;
} else if (k < step && i != items.length - 1) {
k++;
i++;
}
}
output.push(items[0]);
return output;
}
这有效，但效率不高，当我在运行示例测试上运行它时，我得到 5 个示例测试已通过，但它还包括一个 STDERR：执行超时（12000 毫秒）。
样本测试如下：
Test.assertSimilar(josephus([1,2,3,4,5,6,7,8,9,10],1),[1,2,3,4,5,6,7,8,9,10])
Test.assertSimilar(josephus([1,2,3,4,5,6,7,8,9,10],2),[2, 4, 6, 8, 10, 3, 7, 1, 9, 5])
Test.assertSimilar(josephus(["C","o","d","e","W","a","r","s"],4),['e', 's', 'W', 'o', 'C', 'd', 'r', 'a'])
Test.assertSimilar(josephus([1,2,3,4,5,6,7],3),[3, 6, 2, 7, 5, 1, 4])
Test.assertSimilar(josephus([],3),[])
我的问题是，我怎样才能让它更有效率？
是我使用的算法是错误的还是实现？
一条评论提到了两件事：
>
push（）非常慢，这是我的一种可能性（错误的数据结构）
建议查看递归（这更多地涉及我对算法的怀疑）。不过，我并没有真正看到如何使它递归。
提前感谢您的帮助！
有一个复发，这是可以记忆的。(这似乎通过了Codewars测试。)
function g(n, k, i, memo){
if (memo.hasOwnProperty([n, k, i]))
return memo[[n, k, i]];
if (i == 1)
return memo[[n, k, i]] = (k - 1) % n;
return memo[[n, k, i]] =
(k + g(n - 1, k, i - 1, memo)) % n;
}
function f(A, k){
let n = A.length;
let result = new Array(n);
let memo = {};
for (let i=1; i<=n; i++)
result[i - 1] = A[ g(n, k, i, memo) ];
return result;
}
let str = '';
str += JSON.stringify(f([1,2,3,4,5,6,7,8,9,10],1)) + '\n';
//[1,2,3,4,5,6,7,8,9,10])
str += JSON.stringify(f([1,2,3,4,5,6,7,8,9,10],2)) + '\n';
//[2, 4, 6, 8, 10, 3, 7, 1, 9, 5])
str += JSON.stringify(f(["C","o","d","e","W","a","r","s"],4)) + '\n';
//,['e', 's', 'W', 'o', 'C', 'd', 'r', 'a'])
str += JSON.stringify(f([1,2,3,4,5,6,7],3)) + '\n';
//,[3, 6, 2, 7, 5, 1, 4])
str += JSON.stringify(f([],3))
//,[])
console.log(str);
你尝试过实现功能方法吗？来自维基百科:
function getSafePosition(n) {
// find value of L for the equation
valueOfL = n - highestOneBit(n);
safePosition = 2 * valueOfL + 1;
return safePosition;
}
function highestOneBit(i) {
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >> 1);
}
这应该在 O（n） 中运行
你可以把开头部分移到结尾。
const josephus = (x) => parseInt(x.toString(2).substr(1) + 1, 2);
