[leetcode] Python(1)--两数之和(1)、删除排序数组中的重复项(26)
从零开始的力扣(第一天)~
1.两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
—————————————————————————————————————————
题目很简单,想法一般有两种:
1.按续查找,两个for循环,但是这样做的时间复杂度会极高
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
rtype = []
l = len(nums)
for i in range(l):
for j in range(i+1,l):
if target - nums[i] == nums[j]:
rtype = [i,j]
return rtype
可以说是很low了。
2.建立字典,字典内进行查找
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
d = {}
for i,num in enumerate(nums):
if target - num in d:
return [i,d[target - num]]
else:
d[num] = i
从时间上来看,使用字典可以很大程度上的减少时间复杂度。
其中比较重要的几个知识点:
1.刚开始写入一个空字典,并且在最底下给d赋值,d[num] = i,代码的字典值不是一次给完的,而是试,如果不是target - num,就直接存入字典,继续计算,如果是target - num,那么都计算出结果了,后面都不用存了,节省空间。
2. enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。
2.删除排序数组中的重复项
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
—————————————————————————————————————————
因为题目中要求不适用额外的数组空间且空间复杂度为O(1),所以不可以使用set()函数,在参考其他人的做法后,发现这个方法比较易于理解:
1.从后向前查找,若出现重复项,则删除后一位重复数
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 1
while len(nums) > 0:
if (len(nums) - i - 1 < 0):
break
elif (nums[len(nums) - i] == nums[len(nums) - i - 1]):
del nums[len(nums) - i]
else:
i = i + 1
return len(nums)
我自己写了一个从前向后查找的,但是时间却有些长,放上来参考一下:
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
while len(nums) > 0:
if (i > len(nums) - 1):
break
elif (nums.count(nums[i])) > 1:
del nums[i]
else:
i = i + 1
return len(nums)
2.将数组从前向后递归,每当出现一个与前一数不同时,写入此数
class Solution:
def removeDuplicates(self, nums):
if not nums:
return 0
i = 0
for k in range(len(nums)):
if k == 0 or nums[k] != nums[k-1]:
nums[i] = nums[k]
i += 1
return i
这个方法相对于前两种在思路上比较容易,是很好的方法!
以上就是今日经验!