283. Move Zeroes@python

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [,1,,3,12]

Output: [1,3,12,0,0]

原题地址: Move Zeroes

难度: Easy

题意:将数组内的0数移到数组末尾,非0值需要保证相对位置不变,比如上面例子中,非0值的顺序为 1, 3, 12 ,结果也得保证这个顺序

思路1:有点像冒泡,将数组0一个一个的移到末尾

代码描述:

循环{

    如果值为0
　　　　　循环{

        　　当前值与下一个值交换
　　　　　}
}

代码:

n = len(nums)

i = 0

while i < n:

    if nums[i] == 0:

        j = i

        while j < n-1:

            nums[j], nums[j+1] = nums[j+1], nums[j]

            j += 1

        n -= 1
        i -= 1
　　i += 1

时间复杂度:O(n^2)

空间复杂度:O(1)

思路2:

先想一想,对数组进行一次遍历可以知道什么信息或者将数组改变成什么样子?

(1)可以找到任意一个数的位置(快排),存在数字交换

(2)找到最大(小)值(冒泡)

(3)统计各个数的个数

再看看快排(原地):

2    8    7    1    3    5    6     
将4作为分割点

2    1    3    4    8    7    5    6

一次排序之后,元素的相对位置没有改变,可以模仿这种写法,将非0数都移到数组的前面

代码:

class Solution(object):

    def moveZeroes(self, nums):

        """

        :type nums: List[int]

        :rtype: void Do not return anything, modify nums in-place instead.

        """

        n = len(nums)

        idx = -1

        for i in range(n):

            if nums[i] != 0:

                idx += 1

                nums[idx], nums[i] = nums[i], nums[idx]

时间复杂度:O(n)

空间复杂度:O(1)

巴特西

283. Move Zeroes@python

最新文章

热门文章