Twice linear

发表于 | 分类于

题目描述

Consider a sequence u where u is defined as follows:
1 . The number u(0) = 1 is the first one in u.
2 . For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in utoo.
3 . 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…

  • Task: Given parameter n the function dbl_linear (or dblLinear…) returns the element u(n) of the ordered (with <) sequence u.
  • Example: dbl_linear(10) should return 22
  • Note: Focus attention on efficiency

我的代码

function dblLinear(n) {
    // your code
    var res = [1];
    var i=0,j=0;
    while(res.length <= n){
      var y = res[i]*2+1;
      var z = res[j]*3+1;
      if(y<z){
        res.push(y);
        i++;
      }else if(y==z){
        res.push(y);
        i++;
        j++;
      }else{
        res.push(z);
        j++;
      }
    }
    return res[n];
}

Clever

function dblLinear(n) { 
var ai = 0, bi = 0, eq = 0; 
var sequence = [1]; 
while (ai + bi < n + eq) { 
 var y = 2 * sequence[ai] + 1; 
 var z = 3 * sequence[bi] + 1;
 if (y < z) { 
  sequence.push(y);
  ai++; 
 } else if (y > z) {
  sequence.push(z);
  bi++;
 } else { 
  sequence.push(y);
  ai++; bi++; eq++; 
 }
}
 return sequence.pop();
}

Key

  • 考虑效率问题，就不能将所有值都放入数组，再来排序，去重；且这种解法，不好控制循环的次数；
  • 想到在push元素进数组时就按从小到大的顺序放入，且遇到相同的元素就只push一次进数组
  • 具体思路就是每次将y和z中较小的一个放入数组，同时其对应的计数器+1；若y和z相等，放任意一个进数组，两个计算器都+1
-------------完-------------