Authored by Tony Feng

Created on April 16th, 2022

Last Modified on April 16th, 2022

Task 1 - Q04. 二维数组中的查找

Question

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
e.g.
[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]

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if matrix == [] or matrix == [[]]:
            return False

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

Explanation

• Using the properties of the matrix properly is a trick.
  • The top-right item is the largest number in its row;
  • The top-right item is the smallest number in its column;
• Time Complexity: O(N+M)
• Space Complexity: O(1)

Task 2 - Q50. 第一个只出现一次的字符

Question

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

Solution

1
2
3
4
5
6
7
8
9

class Solution:
    def firstUniqChar(self, s: str) -> str:
        dict = {}
        for c in s:
            dict[c] = not c in dict
        for c in s:
            if dict[c]: 
                return c
        return ' '    

Explanation

• Time Complexity: O(N)
• Space Complexity: O(1)
  • At most 26 keys are in the dictionary.