Problem: 283. 移动零
思路
给定一个数组 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
解题方法
- 可以使用双指针的方法来实现这个功能。一个指针用于遍历数组,另一个指针用于记录当前非零元素应该放置的位置。遍历数组时,将非零元素依次移到非零指针指向的位置,然后将非零指针后面的元素置为零。
- 除了双指针法和逐个移动非零元素到数组前面的方法外,还可以使用一种更简单的方法,即“零元素交换法”。具体步骤如下:
- 使用一个指针 non_zero_pointer 来记录当前非零元素应该存放的位置。
- 遍历数组,当遇到非零元素时,将其与 non_zero_pointer 指向的位置进行交换,并将 non_zero_pointer 后移一位。
这种方法的优点是不需要额外的循环来将剩余位置置为零,只需要一次遍历数组即可完成操作。
复杂度
时间复杂度:
- 遍历数组的时间复杂度为O(n),其中n是数组的长度。
- 第一个循环中的每个操作都是O(1)的时间复杂度,总体时间复杂度为O(n)。
空间复杂度:
- 函数中使用了一个额外的非零指针
non_zero_pointer
,以及一个循环中的临时变量i
,它们都是O(1)的空间复杂度。- 总体空间复杂度为O(1)。
代码
解法一:文章来源:https://www.toymoban.com/news/detail-836249.html
class Solution(object):
def moveZeroes(self, nums):
non_zero_pointer = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[non_zero_pointer] = nums[i]
non_zero_pointer += 1
for i in range(non_zero_pointer,len(nums)):
nums[i] = 0
解法二:文章来源地址https://www.toymoban.com/news/detail-836249.html
class Solution(object):
def moveZeroes(self, nums):
non_zero_pointer = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[non_zero_pointer], nums[i] = nums[i] ,nums[non_zero_pointer]
non_zero_pointer += 1
到了这里,关于力扣代码学习日记五的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!