數(shù)組——Remove Duplicates from Sorted Array

描述

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].

要求時(shí)間復(fù)雜度為O（n）,空間復(fù)雜度為O（1）

#include <iostream>
#include <assert.h>
#include <vector>
#include <algorithm>
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是數(shù)組元素的個(gè)數(shù)

first為第一個(gè)元素下標(biāo)，second為第二個(gè)元素下標(biāo)（如果數(shù)組只有一個(gè)元素，則不會(huì)進(jìn)入循環(huán)，而是直接返回1）

index為復(fù)制后數(shù)組的個(gè)數(shù)

運(yùn)行結(jié)果：

測(cè)試數(shù)組為 char a[16] = { 1, 1, 1, 2, 2, 2,2,5 ,6,6,6,6,7,7,8,9};

以下是參考LeetCode中使用STL實(shí)現(xiàn)的代碼

代碼1：

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

所使用的函數(shù)：

template <class ForwardIterator>
  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<class T1,class T2>
	T2 _removeDuplicates(T1 first, T1 last, T2 output)
	{
		while (first != last){
			*output++ = first;
			first = upper_bound(first,last,*first);
		}
		return output;
	}
};

所使用的函數(shù)：

template <class ForwardIterator, class T>
  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]

要求時(shí)間復(fù)雜度為O（n）,空間復(fù)雜度為O（1）

class Solution2
{
public:
	int removeDuplicates(int a[], size_t len)
	{
		return _removeDuplicates(a,a+len,a)-a;
	}
	template<class T1,class T2>
	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;
	}
};

以上代碼是我自己根據(jù)上題中使用STL進(jìn)行部分代碼修改實(shí)現(xiàn)成功的程序

運(yùn)行結(jié)果：

測(cè)試數(shù)組為 int a[16] = { 1, 1, 1, 2, 2, 2,2,5 ,6,6,6,6,7,7,8,9};

以下是參考LeetCode中實(shí)現(xiàn)的代碼

代碼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<len-1 && a[i] == a[i - 1] && a[i] == a[i + 1])
				continue;
			a[index++] = a[i];
		}
		return index;
	}
};