Remove Element(删除重复元素，循环删除2个及2个以上元素)

Dear 丶 2022-08-07 19:30 137阅读 0赞

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

时间复杂度O(n)，空间复杂度O(1)。解题思路，主要就是双指针的思想，一个为游标遍历，一个为新数组的最后一个元素：

public int removeElement(int[] A, int elem) {
            int j = -1;
            for (int i = 0; i < A.length; i++) {
            	if (A[i] != elem) {
            		A[++j] = A[i];
            	}
            }
            return j+1;
        }

这种解法思路很重要，因为后面很多题都是这个题的变形，特别麻烦。

变形题，如果删除的不是一个元素，而是两个呢？比如删除1,2。必须考虑循环删除的示例比如，21112223，删除1,2元素之后，就变成了23，因为中间的23删除之后，数组还有连续元素。

此题的难度里面就上去了，但是有了上一题的铺垫，下面就比较好解了。但是也是有差别了，主要思想就是栈的结构。先上代码：

public int removeElement(int[] A, int elem1, int elem2) {
        	int i = -1;
        	for (int j = 0; j < A.length; j++) {
        		if (A[j] != elem2) {
        			A[++i] = A[j];
        		} else if (i >= 0 && A[i] == elem1){ //A[i] == elem1 && A[j] == elem2
        			i--;
        		} else { //A[i] != elem1 && A[j] == elem2
        			A[++i] = A[j];
        		}
        	}
        	return i+1;
        }

其中用到了，栈的思想。但是别没有开辟栈空间，而是在原来数组的基础上模仿这个栈。i一直指向的是栈顶位置，j是将要入栈的元素。主要有三个判断：

第一个if语句的含义是：如果没有遇到elem2，则元素一直入栈。

第一个if语句的含义是：如果此时栈顶元素为elem1，并且将要入栈的元素是elem2，即形成了连续的元素elem1,elem2。故出栈，i--。

第二个if语句的含义是：如果栈顶不是elem1，则继续入栈。当然，更加简洁的是第一个跟第二个if语句合并一块，但是代码的阅读难度比较大。