最近看到一道面试题，面试官说是算法题。我粗略看了下，努力在其中寻找数学公式，但是最后发现它算是一个数据结构相关的题目，没有算法层面的知识。

// There is an array generated by a rule.
// The first item is 1. If k is in the array, then k3 +1 and k2+1 are in the array.
// The array is sorted. There are no duplicate values.
// Please write a function that accepts an input N. It should return the index N of the array.
// For example [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, …] n=10, return 22
function getNumberFromTheArray(N) {
return 22;
}
console.log(getNumberFromTheArray(5)) // 10;
console.log(getNumberFromTheArray(10)) // 22;

这题大体意思是有序数组是由数组中的数字K，以及3K+1、2K+1构成，即这是一个迭代生成的问题。然后通过下标找到数组中的值。
我们先看数组中相邻的两个数组（X, Y），假设Y = X+n。则通过X生成的数字是

• 2X+1
• 3X+1
  通过Y生成的数字是：
• 2Y+1=2(X+n)+1
• 3Y+1=3(X+n)+1
  基于上面的式子我们可以得出
• 2X+1<2Y+1
• 3X+1<3Y+1
  但是不能确定3X+1和2Y+1的大小。
  这样可以确定的是：我们通过相邻的两个数字（X，Y），只能确定最小的数字是2X+1。
  后面的思路也是基于这个展开。
  2K+1和3K+1数组是递增的，所以新的数据产生后只要向其尾部插入即可。
  一旦游标的位置移动到结果数字的最后一位，就会触发2K+1和3K+1数组第一个元素的对比，然后将小的数字从原数组中删除，并插入到结果数组的最后一位。
  

class ValueGenerator:
    def __init__(self, start):
        self._start_value = start
        self._calc_index = -1
        self._2k_plus_1 = []
        self._3k_plus_1 = []
        self._sorted = [start]

    def get_number_from_the_array(self, index):
        self._index = index
        return self._calc(self._start_value)
    
    def _calc(self, value):
        while self._calc_index < self._index:
            if self._calc_index + 1 < len(self._sorted):
                value = self._sorted[self._calc_index + 1]
                self._2k_plus_1.append(2*value + 1)
                self._3k_plus_1.append(3*value + 1)
                self._calc_index = self._calc_index + 1
            else:
                if len(self._2k_plus_1) == 0 and len(self._3k_plus_1) == 0: 
                    return -1
                elif len(self._2k_plus_1) == 0:
                    self._sorted.append(self._3k_plus_1[0])
                    self._3k_plus_1.remove(self._3k_plus_1[0])
                elif len(self._3k_plus_1) == 0:
                    self._sorted.append(self._2k_plus_1[0])
                    self._2k_plus_1.remove(self._2k_plus_1[0])
                else:
                    _2K_plus_1 = self._2k_plus_1[0] if len(self._2k_plus_1) > 0 else 0
                    _3K_plus_1 = self._3k_plus_1[0] if len(self._3k_plus_1) > 0 else 0
                    cur_min_value = 0
                    
                    if _2K_plus_1 < _3K_plus_1:
                        cur_min_value = _2K_plus_1
                        self._2k_plus_1.remove(cur_min_value)
                    elif _2K_plus_1 == _3K_plus_1:
                        cur_min_value = _3K_plus_1
                        self._2k_plus_1.remove(cur_min_value)
                        self._3k_plus_1.remove(cur_min_value)
                    else:
                        cur_min_value = _3K_plus_1
                        self._3k_plus_1.remove(cur_min_value)

                    if self._sorted[-1] < cur_min_value:
                        self._sorted.append(cur_min_value)
        return self._sorted[self._index]
                
            
if __name__ == "__main__":
    value_generator = ValueGenerator(1)
    print(value_generator.get_number_from_the_array(1))
    print(value_generator.get_number_from_the_array(10))
    print(value_generator.get_number_from_the_array(100))
    print(value_generator.get_number_from_the_array(1000))
    print(value_generator.get_number_from_the_array(10000))
    print(value_generator.get_number_from_the_array(100000))
    print(value_generator.get_number_from_the_array(1000000))