剑指Offer-数组与矩阵专题

3. 数组中重复的数字

题目描述

在一个长度为n的数组里，所有数字在0到n-1的范围内。数组中某些数字是重复的，但是不知道有几个数字重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:
[2, 3, 1, 0, 2, 5]

Output:
2

题解

思路1（位置重排）：
数组长度在0到n-1的范围内，如果数字没有重复，则这些数字排序后将会和下标一一对应。因此，可遍历数组，每次检查数字与下标是否一致，一致说明它在属于它的位置上，如果不一致则将其交换到该数字作为下标的位置上，如果交换过程中，那个位置已经出现等于它下标的数字，则出现了重复。

时间复杂度 O(n)，空间复杂度O(1)

位置重排

class Solution:
    def duplicate(self, nums):
        for i in range(len(nums)):
            if nums[i] == i:
                continue
            else:
                if nums[i] == nums[nums[i]]:
                    return nums[i]
                else:
                    nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        
        return -1
    

if __name__ == "__main__":
    nums = [2, 3, 1, 0, 2, 5]
    print(Solution().duplicate(nums))

思路2（哈希表）：
使用哈希表记录元素出现的次数，如果遇到元素已经在哈希表上出现过，则它就重复了。

时间复杂度 O(n)，空间复杂度O(n)

class Solution:
    def is_duplicate(self, nums):
        hash_map = dict()
        for num in nums:
            if num in hash_map:
                return num
            else:
                hash_map[num] = 1
        
        return -1
    

if __name__ == "__main__":
    nums = [2, 3, 1, 0, 2, 5]
    print(Solution().is_duplicate(nums))

4. 二维数组中的查找

题目描述

给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在二维数组中。


Input:
array = [
  [1,2,8,9],
  [2,4,9,12],
  [4,7,10,13],
  [6,8,11,15]
]
target = 7

Output:
True

题解

思路（二分查找）：
根据题意，二维数组的左下元素要大于它上方的元素，小于它右方的元素，而右上元素要大于它左方的元素，小于它下方的元素，利用此心智，将查找部分分成一个大区间和一个小区间。先获取数组的两个边长，判断特殊情况，然后以左下角元素为起点，若它是小于目标元素，则往右移动索引，若大于目标元素，则向上移动索引，如果移动到数组边界也没找到，则说明数组中不存在目标元素。

时间复杂度 O(m + n)，空间复杂度O(1)

二分查找

class Solution:
    def find_target(self, target, array):
        if len(array) == 0 or len(array[0]) == 0:
            return False
        row, col = len(array), len(array[0])
        i, j = row - 1, 0
        while i >= 0 and j < col:
            if target == array[i][j]:
                return True
            elif target < array[i][j]:
                i -= 1
            else:
                j += 1
        
        return False
    

if __name__ == "__main__":
    array = [
      [1,2,8,9],
      [2,4,9,12],
      [4,7,10,13],
      [6,8,11,15]
    ]
    target = 7
    print(Solution().find_target(target, array))

True

5. 替换空格

题目描述

将一个字符串中的空格替换成"%20"

Input:
"We Are Happy"

Output:
"We%20Are%20Happy"

题解

思路（字符串相加）：
遍历字符串，如果字符为空格，则替换成%20，如果不是，则直接复制。

字符串相加

时间复杂度 O(n)，空间复杂度O(n)

class Solution:
    def replace_space(self, s):
        res = ""
        for ch in s:
            if ch == " ":
                res += "%20"
            else:
                res += ch
        
        return res


if __name__ == "__main__":
    s = "We Are Happy"
    print(Solution().replace_space(s))

We%20Are%20Happy

29. 顺时针打印矩阵

题目描述

按照顺时针的方向，从外到里打印矩阵的值。

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16]
]

Output:
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

题解

思路（模拟）：
一层一层从外到里打印，观察可知每一层打印都有相同的处理方式，唯一不同的是上下左右边界的不同。打印顺序为：从左到右打印一行->从上到下打印一行->从右到左打印一行->从下到上打印一行。

时间复杂度O(mn)，空间复杂度O(1)

class Solution:
    def print_matrix(self, matrix):
        res = []
        r1, r2, c1, c2 = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
        while r1 <= r2 and c1 <= c2:
            for i in range(c1, c2 + 1):
                res.append(matrix[r1][i])
            for j in range(r1 + 1, r2 + 1):
                res.append(matrix[j][c2])
            if r1 != r2:
                for w in range(c2 - 1, c1 - 1, -1):
                    res.append(matrix[r2][w])
            if c1 != c2:
                for k in range(r2 - 1, r1, -1):
                    res.append(matrix[k][c1])
            r1 += 1
            r2 -= 1
            c1 += 1
            c2 -= 1

        return res
    

if __name__ == "__main__":
    matrix = [
      [1,2,3,4],
      [5,6,7,8],
      [9,10,11,12],
      [13,14,15,16]
    ]
    print(Solution().print_matrix(matrix))

[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

50. 第一个只出现一次的字符

题目描述

在一个长为n的字符串中找到第一个只出现一次的字符，并返回它的位置，如果没有则返回-1。

Input:
"google"

Output:
4

题解

思路（哈希表）：
首先遍历字符串，使用哈希表对每个字符出现次数进行统计，然后再遍历字符，遇到哈希表统计次数为1的字符就是第一个只出现一次的字符。

时间复杂度O(n)，空间复杂度O(1)

class Solution:
    def first_not_repeating_char(self, strs):
        hash_map = dict()
        for s in strs:
            if s in hash_map:
                hash_map[s] += 1
            else:
                hash_map[s] = 1
        for i in range(len(strs)):
            if hash_map[strs[i]] == 1:
                return i

        return -1
    

if __name__ == "__main__":
    strs = "google"
    print(Solution().first_not_repeating_char(strs))

参考文章

本文是笔者通过下列网站学习的记录，有部分修改和补充，转载请注明出处，并附带下面链接。