剑指 Offer 03. 数组中重复的数字(python3编写)
2022/1/28 17:35:05
本文主要是介绍剑指 Offer 03. 数组中重复的数字(python3编写),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
- 1、题目描述:
- 2、方法一:排序
- 思路:
- 代码:
- 3、方法二:哈希表
- 思路:
- 代码:
- 4、方法三:原地交换
- 思路:
- 代码:
1、题目描述:
2、方法一:排序
思路:
首先将数组从小到大排序;然后再遍历一遍数组,检查相邻元素是否相等,若相等则找到了一个重复的元素,直接返回这个元素即可。
代码:
class Solution: def findRepeatNumber(self, nums: List[int]) -> int: nums.sort() # 从小到大排序 for i in range(1, len(nums)): if nums[i-1] == nums[i]: # 相等则直接返回 return nums[i]
由于要排序,因此时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn);空间复杂度为 O ( 1 ) O(1) O(1)。
3、方法二:哈希表
思路:
方法一主要时间用在了排序上,那么我们不用排序能否做出来呢?这里可以使用哈希表来做记录。具体来说:遍历数组,将元素作为哈希表的key,出现次数作为value,一旦出现次数大于1则直接返回当前元素即可。
代码:
class Solution: def findRepeatNumber(self, nums: List[int]) -> int: hash_table = {} # key为元素,value为出现次数 for i in range(len(nums)): try: hash_table[nums[i]] += 1 return nums[i] # 上面语句没报错,说明重复了 except: hash_table[nums[i]] = 1
时间复杂度为 O ( n ) O(n) O(n);空间复杂度为 O ( n ) O(n) O(n)。
4、方法三:原地交换
思路:
以上两种方法都很朴素,但是一个时间复杂度高,一个空间复杂度高,不足以拿到offer,那么要是面试官要求:时间复杂度为 O ( n ) O(n) O(n);空间复杂度为 O ( 1 ) O(1) O(1)呢?这个题又怎么解决?
直接看官方的解答:
小技巧:如果觉得不好想,用例子模拟,如下面代码这样。
代码:
class Solution: def findRepeatNumber(self, nums: List[int]) -> int: i = 0 for i in range(len(nums)): # 以[0,1,2,3,2,5,3]为例,假设此时i指向第二个2,然后就好理解了 while i != nums[i]: if nums[nums[i]] == nums[i]: # 两个元素相等了 return nums[i] nums[nums[i]], nums[i] = nums[i], nums[nums[i]] # 调整使得:元素和下标对应
注意:代码中尽管有一个两重循环,但每个数组最多只要交换两次就能找到属于它自己的位置,因此总的时间复杂度时 O ( n ) O(n) O(n)。
当然,空间复杂度显然是 O ( 1 ) O(1) O(1)。
这篇关于剑指 Offer 03. 数组中重复的数字(python3编写)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python