LeetCode解题报告(27)--双指针找数组所有特定元素

发表于 标签 ，

原题如下： >Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example: Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

实现思路：双指针遍历，指针1从前往后遍历，指针2从后往前遍历。指针2先往前找到与val值不同的元素，然后停止；接着指针1开始往后找到与val相同的元素，然后指针1和指针2的元素交换，这样便把与val值相同的元素全部扔到了数组末尾。

需要注意的是，虽然该数组提供了删除元素的操作，但是删除一个元素的平均时间复杂度是\(O(n)\),总的时间复杂度为\(O(n^2)\)

还需要注意的是一个溢出的问题，对于一般的编译型语言如Java、C++等int是4个字节的，所以int的范围是\(-2^{31}\) ~ \(2^{31}-1\),但是在python中int在32位系统上占四个字节，在64为系统上占8个字节，可通过sys.maxint查看，而在本题中默认就是4个字节，如果溢出时输出sys.maxint会报错。

实现代码如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        l = 0
        r = len(nums)-1
        while l<r:
            if nums[r] == val:
                r-=1
                continue
            if nums[l] == val:
                nums[l],nums[r] = nums[r],nums[l]
                l += 1
                r -= 1
            else:
                l += 1
        
        if l == r: # 有可能l>r
            if not nums[l] == val:
                l+=1
        return l