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