一个通过下标查找数值的面试题解法

方亮

发布于 2024-03-19 08:25:34

580

发布于 2024-03-19 08:25:34

文章被收录于专栏：方亮方亮

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

// 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))

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除

数组