CodeWars算法 Twice linear 问题

Z时代
2024-01-10
分类：IT

折腾了两天了，一直只是通过测试，但是提交的时候会出错，代码效率太差。求大神指点...
算法如下：
*"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();}