使有序序列中每个元素最多出现2次的几种算法实现

浏览数：25 / 时间：2015年06月08日

问题描述(来源：leetcode——Remove Duplicates from Sorted Array II)

对于一个给定的已排序序列，要求实现一个算法:使序列中同一元素出现的次数不超过2次，对超过2次的同一元素直接删除，例如：

输入：给定序列A={1,1,1,2,2,3}

输出：要求返回length =5,A变为{1,1,2,2,3}

一、实现1

1.方式：该实现使用计数count,比较直观，而较容易想到，且扩展性较好，如果想将条件改为：最多出现n次，只需将条件count！=2改为count= n;

2.代码

int removeDuplicates2(int A[],int n)
{
	if(n<=2) return n;

	int index = 0;
	int count ;
	for(int i=1;i<n;i++)
	{
		//如果发现了新元素：则index向前1，并赋值为新元素，
		if(A[i]!=A[index])
		{
			A[++index] = A[i];
			count = 1;
		//仍然为原元素且count！=2，则index向前并赋值为原元素，同时对count加1
		}else if(count!=2)
		{
			A[++index] = A[i];
			count++;
		}

		//剩余情况：仍然为原元素但count==2，什么也不做，只是继续扫描越过重复元素
	}

	return index+1;

2、实现2

方式：该实现其并不引入count计数，代码思路简洁而巧妙：
1）基于最多不出现2次这样一个事实，因此一旦发现一个与之前新元素的不相同的元素其应该保守地拷贝到该之前新元素后2的位置（保守是因为可能应该放置于后1位置），非常简洁。
2)而巧妙之处体现在去除保守放置分析中

int removeDuplicates2(int A[],int n)
{
	if(n<=2) return n;

	int index =2;
	for(int i=2;i<n;i++)
	{
		if(A[i]!=A[index-2])
		    A[index++]=A[i];
	}
	return index;
}

本文出自 “一半一半” 博客，请务必保留此出处http://4902717.blog.51cto.com/4892717/1589689

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

使有序序列中每个元素最多出现2次的几种算法实现