重庆自助模板建站,行业网站策划,软件开发的自学教程,wordpress 页面如何打开评论283. 移动零
提示
简单
2.3K
相关企业
给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。
请注意 #xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例 1:
输入: nums [0,1,0,3,12]
输出: [1,…283. 移动零
提示
简单
2.3K
相关企业
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。 示例 1:
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入: nums [0]
输出: [0] 提示:
1 nums.length 104-231 nums[i] 231 - 1 进阶你能尽量减少完成的操作次数吗
方法一类似冒泡
用冒泡的思想将前方的0慢慢向后移动
时间复杂度为O(n(n−1)(n−2)…1)O(n^2)
因此给定的算法在最坏情况下具有二次时间复杂度。对于包含大量元素的数组这可能导致性能问题。
class Solution:def moveZeroes(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.for i in range(len(nums)):if nums[i]0:for j in range(len(nums)-1,i,-1):if nums[j]0:continueif nums[j]!0:tempnums[i]nums[i]nums[j]nums[j]temp
方法二双指针
考虑使用双指针法将非零元素向前移动移动完成之后0元素均在数组末端。这样的算法具有线性时间复杂度 O(n)。
class Solution:def moveZeroes(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.left,right0,0while rightlen(nums):if nums[right]!0:nums[left],nums[right]nums[right],nums[left]left1right1
