Leetcode 240：搜尋二維矩陣 II

文章目錄

• 題目描述
• python3解法（Leetcode）
• python2解法（牛客網）
• C++解法（牛客網）
• 小結

題目描述

編寫一個高效的算法來搜尋 m x n 矩陣 matrix 中的一個目标值 target。該矩陣具有以下特性：

每行的元素從左到右升序排列。

每列的元素從上到下升序排列。

示例:

現有矩陣 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
           

給定 target = 5，傳回 true。

給定 target = 20，傳回 false。

python3解法（Leetcode）

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row = len(matrix)
        # col = len(matrix[0])

        i = row-1
        j=0

        while i>=0 and j<len(matrix[0]):
            if matrix[i][j] == target: return True
            elif matrix[i][j] < target: j+=1
            else: i-=1
        return False
           

首先這段代碼執行測試用例可以通過，也可以送出成功：

執行用時 :48 ms, 在所有 Python3 送出中擊敗了56.59%的使用者

記憶體消耗 :18.4 MB, 在所有 Python3 送出中擊敗了7.69%的使用者

但是下面的代碼就隻能通過測試用例，而送出失敗：

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row = len(matrix)
        col = len(matrix[0])

        i = row-1
        j=0

        while i>=0 and j<col:
            if matrix[i][j] == target: return True
            elif matrix[i][j] < target: j+=1
            else: i-=1
        return False
           

錯誤提示在第9行，

Line 9: IndexError: list index out of range

,但我仍然不知道為什麼會出現這種問題，是因為正式送出時所使用的測試矩陣太大了麼？

python2解法（牛客網）

# -*- coding:utf-8 -*-
class Solution:
    # array 二維清單
    def Find(self, target, array):
        # write code here
        row = len(array)
        col = len(array[0])
        
        i = row-1
        j = 0

        while i>=0 and j<col :
            if array[i][j] == target:return True
            elif array[i][j]< target: j+=1
            else: i-=1
        return False
           

運作時間： 217 ms 占用記憶體：5624K

C++解法（牛客網）

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int rows = array.size() - 1, cols = array[0].size();
        int i = rows, j = 0;
        while(i>=0 && j<cols){
            if(array[i][j] == target) return true;
            else if(array[i][j] < target) j++;
            else i--;
        }
        return false;
    }
};
           

運作時間： 9 ms 占用記憶體：1380K

小結

1、通過上述的對比，可以看到C++的優勢，但是人生苦短，我用python

2、LeetCode中遇到的問題，各路大神如知曉問題所在，還請多指點一二