本文共 3348 字，大约阅读时间需要 11 分钟。

1、问题描述

最近遇到一个问题，给出一个有序的二维数组（方阵）（有序指的是对于每一行和每一列元素都是逐渐增大的），然后让你用最快的方法判断某个值是否在这个数组中，如果存在则返回True，反之返回False。例如给出的有序数组如下所示：

array = [[1,2,3],        [4,5,6],        [7,8,9]]

让你判断4是否出现在数组中。

2、不考虑矩阵特点的算法（三种）

解决这个问题的方法有很多，如果不考虑二维方阵本身是有序的特点，那你至少应该想到以下方法：

def find_num_B(num, array):    if len(array[array == num]) != 0:        return True        return False#只使用np.argwhere方法判断def find_num_C(num, array):    if len(np.argwhere(array == num)) != 0:        return True        return False#只使用for循环和列表内置方法判断def find_num_D(num, array):    array = list(array)    for array_ in array:        if num in array_:            return True        return False

3、根据矩阵特点进行的算法优化思路及代码

但是，考虑到二维方阵本身是有序的，我们可以根据二维方阵的特点对算法进行优化，思路如下图所示：

如上图所示，这里只考虑矩阵是二维方阵的情况，实现代码如下：

def find_num_A(num, array):    size_ = array.shape    array_ = np.diagonal(array, offset=0)  #由对角线元素组成的一维数组长度    if len(np.argwhere(array_ == num)) != 0:   #如果元素刚好在对角线上，则返回True        return True        #如果元素不在对角线上，则又要分两种情况，一种是对角线上的元素有比7大的数，则找到比7大的数中的最小数在array_中的位置；反之，则返回array_的长度。    idx_ = np.argwhere(array_ == np.max(array_[array_ < num])) if len(array_[array_ > num]) != 0 else np.array([[len(array_)-1]])    idx_ = idx_[0,0]    print(idx_)    if size_[0] == size_[1]:  #如果列数等于行数，执行该分支        if idx_ + 1 == len(array_):             return False        if len(np.unique(array[idx_+1,0:idx_+1] == num)) == 2 or len(np.unique(array[idx_,idx_+1:] == num)) == 2:            return True            return False

最后做一个比较，比较一下这四种算法的性能：

4、四种结果进行对比

random.seed(66)#array = np.random.randint(10000,size=(10000, 10000))range_ = np.linspace(1,100000000,100000000,endpoint=True, dtype=int)array = range_.reshape((10000,10000))print('数组维度为：%s'%str(array.shape))#num = random.sample(range_,1)num = [7,17777777,27777777,37777777,47777777,57777777,67777777,77777777,87777777,97777777,7777777.7]print('要寻找的数字为：%s'%num)results = [[],[],[],[]]times = [[],[],[],[]]for num_ in tqdm(num):    a = time.time()    results[0].append(find_num_A(num_, array))    b = time.time()    times[0].append(b-a)    a = time.time()    results[1].append(find_num_B(num_, array))    b = time.time()    times[1].append(b-a)    a = time.time()    results[2].append(find_num_C(num_, array))    b = time.time()    times[2].append(b-a)    a = time.time()    results[3].append(find_num_D(num_, array))    b = time.time()    times[3].append(b-a)

5、对比结果

可视化代码：

plt.figure(figsize=(6,4))plt.rcParams['font.sans-serif'] = ['SimHei']plt.rcParams['axes.unicode_minus'] = Falseplt.scatter(np.log(np.array(num)),times[0],marker='^')plt.scatter(np.log(np.array(num)),times[1],marker='*')plt.scatter(np.log(np.array(num)),times[2],marker='+')plt.scatter(np.log(np.array(num)),times[3],marker='o')plt.legend(['算法A','算法B','算法C','算法D'])plt.show()for result in results:    print(result)

四种算法的对比结果如下：

[True, True, True, True, True, True, True, True, True, True, False][True, True, True, True, True, True, True, True, True, True, False][True, True, True, True, True, True, True, True, True, True, False][True, True, True, True, True, True, True, True, True, True, False]

6、结论：

• （1）根据目标矩阵特点开发的算法A与其余三种算法的最终结果完全相同，说明了算法A的结果是可信的；
• （2）从上图可以看出，随着计算规模的增大，算法A、B和C的计算时间基本不变，基本维持在同一量级，计算效率由高到低分别为A>B>C；当计算规模达到2^16左右时，算法D的计算效率迅速下降，时间复杂度程指数增长；
• （3）当目标数值为小数时（num=7777777.7）时，由于原array中不含该数值，算法D遍历了全部数据，其计算时间甚至超过num=777777777时的计算时间；
  综上，算法D的效率是不稳定的，而根据目标数组特点开发的算法A的计算效率是稳定的，且效率最高。

转载地址：http://warti.baihongyu.com/