尽量先将小饼干分配给胃口小的孩子,故而饼干和孩子胃口都应该先排序。
python中,a.sort()只能用于a为list, sort()是可变对象的方法,无参数,无返回值,但会影响改变对象。
sorted()不会发生上述情况,sorted()函数需要一个参数(参数可以是列表、字典、元组、字符串,所有的可迭代序列都行)
只是要注意一点,g和s长度不定,需要确保所有的饼干都可以遍历到且胃口索引没有超出。
class Solution(object):
def findContentChildren(self, g, s):
:type g: List[int]
:type s: List[int]
:rtype: int
g.sort()
s.sort()
i,j=0,0 #while的变量要提前赋值
# count=0
# while i <len(s) and j <len(g):
# if s[i]>=g[j]:
# count+=1
# i+=1
# j+=1
# else:
# i+=1
# # g.popleft() #list没有popleft函数,deque才能这样双端操作
# # del s[0] #进行删除就会改变索引,发生超出索引的情况
# return count
while i <len(s) and j <len(g):
if s[i]>=g[j]:
j+=1
i+=1
return j
复杂度分析:
时间复杂度:O(nlogn+nlongn+n)=O(nlogn)
,sort()为O(nlogn)
空间复杂度:O(1)