python(leetcode)-283移动零
程序员文章站
2023-10-11 21:23:17
说下拿到这道题时的思路: 给人的感觉并不难,首先的想法就是遍历数组中每一个元素,判断如果为0则删除,同时末尾增加0 上代码(通过240ms)击败20%的用户 代码非常简洁,只有短短4行,但是对比其他方法效率却不高, 分析代码的时间复杂度 外层for循环需要N次,remove(i)需要N次,appen ......
给定一个数组 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) 可以发现确实速度快了很多
上一篇: CSS Grid 布局完全指南(图解 Grid 详细教程)
下一篇: 跟老婆两地分居