CodeWars算法 Twice linear 问题
折腾了两天了,一直只是通过测试,但是提交的时候会出错,代码效率太差。求大神指点...
算法如下:
*"Consider a sequence u where u is defined as follows:
The number u(0) = 1 is the first one in u.
For each x in u, then y = 2 x + 1 and z = 3 x + 1 must be in u too.
There are no other numbers in u.
Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]
1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on..."*
我的代码如下`
public static int dblLinear(int n){
ArrayList<Long> arrayresult = new ArrayList<Long>();
arrayresult.add((long) 1);
//循环,生成这样的u[]数组。但是i太大的话,会超时
for (int i = 1; i <= 15; i++)
{
arrayresult = CreateArrayList(arrayresult);
}
System.out.println(arrayresult.toString());
long location = arrayresult.get(n);
return (int)location;
}
public static ArrayList<Long> CreateArrayList(ArrayList<Long> resultArray)
{
ArrayList<Long> tmp = (ArrayList<Long>)resultArray.clone();
for (long single : resultArray)
{
//按照规则,生成y和z。
long y = single * 2 + 1;
long z = single * 3 + 1;
//看看y和z在不在数组里面,不在的话,添加进去。
if (resultArray.indexOf(y) == -1)
{
tmp.add(y);
}
if (resultArray.indexOf(z) == -1)
{
tmp.add(z);
}
}
Collections.sort(tmp);
return tmp;
}
public static void main(String[] args)
{
System.out.println(DoubleLinear.dblLinear(100));
}`
提示错误:"Process was terminated. It took longer than 10000ms to complete
0 Passed"
如果循环的i设置的小,那么数组里面的数字也不完整。归根到底,还是代码效率太差...求指导啊
回答:
function dblLinear(n) { // your code
var arr=[1];
var y=0;
var z=0;
while(arr.length<=n){
if(arr[y]*2 +1 < arr[z] *3 +1){
arr.push(arr[y]*2 +1);
y++;
}else if(arr[y]*2 +1 > arr[z] *3 +1){
arr.push(arr[z]*3 +1);
z++;
}else{
y++;
}
}
return arr[n];
}
javascript写的。
回答:
我今天也遇到了同样的问题;我们俩的算法思路是一样的(同样都超时),所以这可能是算法不够好,我现在仍在想有没有更好的算法,最后百度了下。。。(ps:好重的罪恶感)
下面这两个算法思路不对,都超时(后一个是前一个算法的改进,但依然超时)
function dblLinear(n) { let i = 0,
arr = [1];
while(i<=n){
let x = arr[i],
y = 2 * x + 1,
z = 3 * x + 1;
// 写入数组(跳过重复值)
if(!arr.includes(y)){
arr.push(y);
}
if(!arr.includes(z)){
arr.push(z);
}
// 排序
arr.sort(function(a, b){
return a - b;
});
i += 1;
}
return arr[n];
}
function dblLinear(n) {
let temp = [1],
y = 0,
z = 0,
i = 0,
j = 0,
k = 0;
while (i < n) {
y = temp[i] * 2 + 1;
z = temp[i] * 3 + 1;
// 按顺序插入 y z(避免排序)
for (j=temp.length-1; j>-1; j-=1) {
if (y == temp[j]) {// 避免重复
break;
}
if (y > temp[j]) {// 冒泡插入 y
temp.splice(j + 1, 0, y);
break;
}
}
for (k=temp.length-1; k>-1; k-=1) {
if (z == temp[k]) {
break;
}
if (z > temp[k]) {
temp.splice(k + 1, 0, z);
break;
}
}
i += 1;
}
return temp[n];
}
正确算法
function dblLinear(n) { let ai = 0,
bi = 0,
eq = 0,
sequence = [1];
while (ai + bi < n + eq) {// ai + bi - eq 是 push() 进数组的数的个数
let y = 2 * sequence[ai] + 1,
z = 3 * sequence[bi] + 1;
if (y < z) {// 先把 x y 中较小的压入 sequence
sequence.push(y);
ai++;
} else if (y > z) {
sequence.push(z);
bi++;
} else {
sequence.push(y);
ai++;
bi++;
eq++;
}
}
return sequence.pop();
}
正确算法出处:http://www.cnblogs.com/qingmingsang/articles/5355167.html
以上是 CodeWars算法 Twice linear 问题 的全部内容, 来源链接: utcz.com/p/173734.html