欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 27.Remove Element

程序员文章站 2024-03-22 15:04:34
...

Given an array and a value, remove all instances of that value in place and return the new length.
给定一个数列和一个值,将等于这个值的元素移除并返回最后的数列长度。

思路
我首先想到的办法是用一个index, i去遍历数组,若是不等于给定的值,就将另一个index, start所处的位置的值,等于i的位置的值,也就是nums[start] = nums[i],再将start向后移动。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        start = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[start] = nums[i]
                start += 1
        return start

提交之后,发现耗时比较长,然后看了下discuss里别人的做法,发现特别巧妙。定义一个start和end分别位于数列的最左端和最右端,让start向右遍历,若是等于给定的值,就将这个位置的值与end位置的值交换,并且end位置向左移动一位。这样就可以将所有等于给定值的数都移到start的右边去,最后返回start。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        start = 0
        end = len(nums) - 1
        while start <= end:
            if nums[start] == val:
                nums[start], nums[end], end = nums[end], nums[start], end - 1
            else:
                start += 1
        return start
相关标签: leetcode