资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

数组——RemoveDuplicatesfromSortedArray

描述

创新互联公司坚持“要么做到,要么别承诺”的工作理念,服务领域包括:网站制作、网站设计、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的洞口网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!

Given a sorted array, remove the duplicates in place such that each element appear only once

and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array A = [1,1,2],

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

要求时间复杂度为O(n),空间复杂度为O(1)

#include 
#include 
#include 
#include 
using namespace std;

class Solution
{
public:
	int removeDuplicates(char *a, size_t len)
	{
		assert(a);
		size_t index = 1;
		int first = 0;
		int second = 1;
		while (second < len){
			if (a[second] != a[first]){
				a[index++] = a[second];
				first = second;
			}
			second++;
		}
		return index;
	}
};

以上是我自己看完题目后所编写的程序

分析:

len是数组元素的个数

first为第一个元素下标,second为第二个元素下标(如果数组只有一个元素,则不会进入循环,而是直接返回1)

index为复制后数组的个数

运行结果:

测试数组为 char a[16] = { 1, 1, 1, 2, 2, 2,2,5 ,6,6,6,6,7,7,8,9};

数组——Remove Duplicates from Sorted Array

以下是参考LeetCode中使用STL实现的代码

代码1:

class Solution
{
public:
	int removeDuplicates(char a[], size_t len)
	{
		return distance(a, unique(a, a + len));
	}
};

所使用的函数:

template 
  ForwardIterator unique ( ForwardIterator first, ForwardIterator last );
 distance (InputIterator first, InputIterator last);

代码2:

class Solution
{
public:
	int removeDuplicates(char a[], size_t len)
	{
		return _removeDuplicates(a,a+len,a)-a;
	}
	template
	T2 _removeDuplicates(T1 first, T1 last, T2 output)
	{
		while (first != last){
			*output++ = first;
			first = upper_bound(first,last,*first);
		}
		return output;
	}
};

所使用的函数:

template 
  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last,
                                const T& value );

================================================================


描述

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]


要求时间复杂度为O(n),空间复杂度为O(1)

class Solution2
{
public:
	int removeDuplicates(int a[], size_t len)
	{
		return _removeDuplicates(a,a+len,a)-a;
	}
	template
	T2 _removeDuplicates(T1 first, T1 last, T2 output)
	{
		T1 tmp = first;
		while (first != last){
			if ((tmp!=first-1)&&(*tmp == *(first - 1))){
				*output++ = *(first - 1);
			}
			*output++ = *first;
			tmp = first;
			first = upper_bound(first,last,*first);
		}
		return output;
	}
};

以上代码是我自己根据上题中使用STL进行部分代码修改实现成功的程序

运行结果:

测试数组为 int a[16] = { 1, 1, 1, 2, 2, 2,2,5 ,6,6,6,6,7,7,8,9};

数组——Remove Duplicates from Sorted Array

以下是参考LeetCode中实现的代码

代码1:

class Solution2
{
public:
	int removeDuplicates(int *a,size_t len)
	{
		size_t index = 2;
		for (int i = 2; i < len ; ++i){
			if (a[i] != a[index - 2])
				a[index++] = a[i];
		}
		return index;
	}
};

代码2:

class Solution2
{
public:
	int removeDuplicates(int *a, size_t len)
	{
		int index = 0;
		for (int i = 0; i < len ; ++i){
			if (i>0 && i            
            
                        
网站名称:数组——RemoveDuplicatesfromSortedArray
当前链接:http://cdkjz.cn/article/jichie.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220