【剑指offer】03~05. 数组中的数字（Python 实现）
文章目录
- 前言
- 03. 数组中重复的数字
- 04. 二维数组中的查找
- 05. 替换空格
- 结语
前言
😃 大家好，我是writer桑，这是自己的一个 Python 做题记录，方便自己学习的同时分享出来。
03. 数组中重复的数字
题目描述：
找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
代码实现：
class Solution:
def findRepeatNumber(self, nums: [int]) -> int:
my_set = set()
for num in nums:
if num in my_set:
return num
my_set.add(num)
return -1
if __name__ == '__main__':
s = Solution()
nums = [2, 3, 1, 0, 2, 5, 3]
print(s.findRepeatNumber(nums))
提交结果：
思路分析：
- 首先创建一个集合 my_set
- 循环遍历列表 nums 中的元素，如果元素不在集合中则直接添加，如果在集合中则证明这个元素是重复的，直接返回。
- 返回 -1 表示没有发现重复元素
代码实现2：
from typing import List
from collections import Counter
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
count_nums = Counter(nums) # 使用Counter类列出列表中元素出现的次数
sort_nums = sorted(count_nums, key = count_nums.get) # 以元素出现的次数进行升序排序
return sort_nums[-1]
if __name__ == '__main__':
s = Solution()
nums = [2, 3, 1, 0, 2, 5, 3]
print(s.findRepeatNumber(nums))
提交结果2：
思路分析：
- 需要导入第三方库 collections 中的 Counter 类
- 使用 Counter 方法列出列表中元素出现的次数
- 使用 sorted 方法以元素出现的次数为基准进行升序排序，返回一个列表 sort_nums
- 那么列表 sort_nums 最后一个元素一定是出现2次以上的元素（前提是列表一定包含重复元素，如果没有重复元素就没有返回值）
04. 二维数组中的查找
题目描述：
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
现有矩阵 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。
代码实现：
from typing import List
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix) == 0 or matrix == None:
return False
i, j = len(matrix) - 1, 0
while i >= 0 and j < len(matrix[0]):
if matrix[i][j] > target:
i -= 1
elif matrix[i][j] < target:
j += 1
else:
return True
return False
if __name__ == "__main__":
s = Solution()
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
print(s.findNumberIn2DArray(matrix, target))
提交结果：
思路分析：
- 将矩阵逆时针旋转 45° 并展开，可以发现类似于二叉搜索树， 那么从根节点开始搜索时，遇到比 target 大的元素就向左，反之则向右，以此来找到目标值 target 。
- 需要事先判断 matrix 是否为空，为空直接返回 false 。根据二叉搜索树的特性，选用矩阵的左下角的元素作为标志数 flag，若 flag > target ，则 target 一定在 flag 所在 行的上方, 若 flag < target ，则 target 一定在 flag 所在 列的右方，以此类推直到找到目标数 target 。
- 算法本身比较好理解，难点在于根据题目的描述找到突破口。
代码实现2：
from typing import List
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
for arr in matrix:
if target in arr:
return True
return False
if __name__ == "__main__":
s = Solution()
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
print(s.findNumberIn2DArray(matrix, target))
提交结果2：
思路分析：
- 简单的循环输出，逐个数组进行判断有无包含目标数，有则直接返回 true 。当循环结束时，也即表示没有该目标数，返回 false 。
- 对比第一种解法，代码量更少， 但是因为每次都需要逐个遍历数组，所以有时候性能较低，更推荐第一种解法。
05. 替换空格
题目实现：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例：
输入：s = “We are happy.”
输出：“We%20are%20happy.”
代码实现：
class Solution:
def replaceSpace(self, s: str) -> str:
return "%20".join(s.split(' '))
if __name__ == "__main__":
s = Solution()
my_str = "We are happy."
print(s.replaceSpace(my_str))
提交结果：
思路分析：
- 使用 split 方法指定空格 ’ ’ 进行分割，再使用 join 方法指定 “%20” 进行连接， 然后直接返回即可。
- 这种解法很容易想到，而且代码量很少、很简洁，一行代码搞定。
代码实现2：
class Solution:
def replaceSpace(self, s: str) -> str:
res = []
for i in s:
if i == ' ':
res.append("%20")
else:
res.append(i)
return "".join(res)
if __name__ == "__main__":
s = Solution()
my_str = "We are happy."
print(s.replaceSpace(my_str))
提交结果2：
思路分析：
- 声明列表 res 用于存放返回结果，for 循环遍历字符串 s 依次判断字符元素， 如果为空格 ’ ’ 则替换为"%20"放入 res , 如果不为空格则直接放入 res 中。循环结束使用 join 方法连接 res 列表返回即可。
- 与第一种解法相比，这种解法更常见，代码量较多，两者在性能上前者更好一点。
结语
🌻 以上就是本次的做题记录啦，希望大家看完有所收获。