Leetcode-80-Remove Duplicates from Sorted Array II

 

Remove Duplicates from Sorted Array II

 

 

 

来自 <https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/>

 

Follow up for "Remove Duplicates":

 

What if duplicates are allowed at most twice?

 

For example,

 

Given sorted array nums = [1,1,1,2,2,3],

 

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

 

题目解读：

 

上接“Remove Duplicates”，如果每个重复的元素最多允许重复两次呢？例如给定一个有序数组nums=[1,1,1,2,2,3]，函数运行结果返回5，并且数组中的前五个元素为1，1，2，2，3.

 

解析：在原来的程序基础之上加一个计数器count的功能，如果count大于2，则删除后面重复的元素，否则继续遍历数组。

 

Java代码：

public static int removeDuplicates(int[] nums) {
		/**
		 * k 用来记录当前位置和前一个非重复元素之间的相隔元素个数
		 */
		int k=0;
		/**
		 * 用来记录当前元素的重复个数
		 */
		int count=1;
		for (int i=1; i<nums.length; i++) {
			/**
			 * 如果第i-1个元素和第i个元素相同并且为重复元素，则当前位置
			 * 和前一个非重复元素间的间隔加1
			 */
			if((nums[i-1] == nums[i]) && (count>=2)) {
				k++;
				continue;
			} else {
				if(nums[i-1] == nums[i]) {
					count++;
				} else {
					count=1;
				}
				nums[i-k] = nums[i];
			}
		}
		return nums.length-k;
	}

 算法性能：