一小时看懂财务报表,夏琦薇,伊拉克女性示威is
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。
说下拿到这道题时的思路:
给人的感觉并不难,首先的想法就是遍历数组中每一个元素,判断如果为0则删除,同时末尾增加0
上代码(通过240ms)击败20%的用户
1 class solution: 2 def movezeroes(self, nums): 3 """ 4 :type nums: list[int] 5 :rtype: void do not return anything, modify nums in-place instead. 6 """ 7 for i in nums: 8 if(i==0): 9 nums.remove(i) 10 nums.append(0) 11 12 13 if __name__=="__main__": 14 s=solution() 15 nums=[0,1,0,3,12] 16 print(s.movezeroes(nums))
代码非常简洁,只有短短4行,但是对比其他方法效率却不高,
分析代码的时间复杂度
外层for循环需要n次,remove(i)需要n次,append()方法1次
所以时间复杂度为o(n^2)
换一种方法,上代码(通过) 56ms 击败99%
1 class solution: 2 def movezeroes(self,nums): 3 """ 4 5 :param nums: 6 :return: 7 """ 8 count=0 9 zero=0 10 for i in range(len(nums)): 11 if(nums[i]!=0): #判断是否为0 12 nums[count]=nums[i] #不是0的数向前移 13 count+=1 #移动一个 计数加一 14 else: 15 zero+=1 16 for j in range(count,len(nums)): #把最后位置补0 17 nums[j]=0 18 return nums 19 if __name__=="__main__": 20 s=solution() 21 nums=[0,1,0,3,12] 22 print(s.movezeroes(nums))
思路在代码中有注释
分析下时间复杂度:
for循环有n次,if语句1次,赋值语句1次,++1次
第二个for循环n次,赋值语句1次
两个for循环是并列关系 所以时间复杂度为o(n) 可以发现确实速度快了很多
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
Python爬虫:Request Payload和Form Data的简单区别说明
浅谈Python中threading join和setDaemon用法及区别说明
Python3-异步进程回调函数(callback())介绍
python继承threading.Thread实现有返回值的子类实例
Python中使用threading.Event协调线程的运行详解
网友评论