劍指Offer-001：二維陣列中的查找-有解無憂

一、前言

本系列文章為《劍指Offer》刷題筆記，

刷題平臺：牛客網

二、題目

在一個二維陣列中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增排序，請完成一個函式，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數，

1、思路

首先選取陣列中右上角的數字，如果該數字等于要查找的數字，查找程序結束；如果該數字大于要查找的陣列，剔除這個數字所在的列；如果該數字小于要查找的數字，剔除這個數字所在的行，也就是說如果要查找的數字不在陣列的右上角，則每一次都在陣列的查找范圍中剔除一行或者一列，這樣每一步都可以縮小查找的范圍，直到找到要查找的數字，或者查找范圍為空，

2、舉例

如果在一個二維陣列中找到數字7，則回傳True，如果沒有找到，則回傳False，

查找程序如下：

3、編程實作

#! /usr/bin/env python3
# -*- coding:utf-8 -*-

# Author   : Ma Yi
# Blog     : http://www.cnblogs.com/mayi0312/
# Date     : 2020-04-22
# Name     : test01
# Software : PyCharm
# Note     : 在一個二維陣列中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增排序，請完成一個
#            函式，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數，


class Solution:
    # array 二維串列
    @staticmethod
    def find_num(target, array):
        # write code here
        i_rows = len(array)  # 行
        i_cols = len(array[0])  # 列
        if i_rows == 0 or i_cols == 0:
            return False
        i_row = 0
        i_col = i_cols - 1
        while i_row < i_rows and i_col >= 0:
            if target == array[i_row][i_col]:
                return True
            elif target < array[i_row][i_col]:
                i_col -= 1
            else:
                i_row += 1

        return False


def main():
    l_array = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
    result = Solution.find_num(7, l_array)
    print(result)

if __name__ == '__main__':
    main()

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/155300.html

標籤：Python

上一篇：Servlet

下一篇：劍指Offer-002：替換空格