leetcode26.Remove Duplicate

发表于 更新于 分类于 ，

题目要求：输入一个数组和一个值，删除数组中等于该值得元素。不允许分配新的内存空间（即不允许创建新的数组），允许数组中的元素的顺序发生变化，只要该数组在返回长度前的值正确
例如：输入nums = [3,2,2,3], val = 3，程序返回2，且nums数组的前两个值均为2

使用一个指针
时间复杂度O(n), 空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @author rale
 * 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.
 */
public class RemoveElement {
    
    public int removeElement(int[] nums, int val) {
        int index = 0;
        for(int i = 0 ; i<nums.length ; i++){
            if(nums[i] != val){
                nums[index]=nums[i];
                index++;
            }
        }
        return index;
    }
}

使用两个指针
时间复杂度O(n) 空间复杂度O(1)

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
27
28
29
30
31
/**
 * @author rale
 * 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.
 */
public class RemoveElement {
    
    public int removeElement(int[] nums, int val) {
        if(nums==null || nums.length==0){
            return 0;
        }
        int leftPointer = 0;
        int rightPointer = nums.length-1;
        while(leftPointer<=rightPointer){
            if(nums[rightPointer]==val){
                rightPointer--;
                continue;
            }
            if(nums[leftPointer]==val){
                nums[leftPointer] = nums[rightPointer];
                rightPointer--;
            }
            leftPointer++;
        }
        return rightPointer+1;
    }
}

leetcode的测试用例得出的性能分析发现，使用一个指针比使用两个指针的速度更快。但是在数组的容量非常大且数组中该数字出现频率不高的情况下，使用两个指针可以明显减少程序遍历数组的时间。
leetcode上也给出了参考答案