LeetCode-Remove Duplicates from Sorted Array II （删除重复元素，使重复次数最多N次）

电玩女神 2022-08-07 03:54 56阅读 0赞

Follow up for "Remove Duplicates":  
What if duplicates are allowed at most twice?

For example,  
Given sorted array A = `[1,1,1,2,2,3]`,

Your function should return length = `5`, and A is now `[1,1,2,2,3]`.

可以先看另外一道题，[http://blog.csdn.net/my\_jobs/article/details/43453177][http_blog.csdn.net_my_jobs_article_details_43453177]，这个是加强版的。其实仿照上题，改造好的代码如下：

public int removeDuplicates(int[] A) {
        	if (A.length < 3) {
         	   return A.length;
            }
            int j = 0;
            for (int i = 1; i < A.length; i++) {
            	if (A[j] != A[i] || (A[j] == A[i] && (j == 0 || A[j] != A[j-1]))) {
            		A[++j] = A[i];
            	}
            }
            return j+1;
        }

只是在if语句中，加了更严谨的条件判断。

此题可以再加强一下，如果重复元素最后允许出现3次呢？5次呢？或者直接n次？怎么解？可以说思路基本一样，只不过需要判断新数组中重复元素的个数，如果超过n就不需要复制了。上代码：

public int removeDuplicates(int[] A, int n) {
        	if (A.length < n+1) {
        		return A.length;
        	}
        	int j = 0; 
        	int s = 0;
        	for (int i = 1; i < A.length; i++) {
        		if (A[j] != A[i]) {
        			A[++j] = A[i];
        			s = j;
        		} else if (A[j] == A[i] && j - s < n-1) {
        			A[++j] = A[i];
        		}
        	}
        	return j+1;
        }

i和j的含义同上，只不过加了一个s起始位，表示此元素的起始位，用j-s来计算重复元素的个数。

[http_blog.csdn.net_my_jobs_article_details_43453177]: http://blog.csdn.net/my_jobs/article/details/43453177