數(shù)組——RemoveDuplicatesfromSortedArray-創(chuàng)新互聯(lián)

描述

成都創(chuàng)新互聯(lián)長期為上千多家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為榆中企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計、成都做網(wǎng)站，榆中網(wǎng)站改版等技術(shù)服務(wù)。擁有十余年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

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

要求時間復(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ù)組元素的個數(shù)

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

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

運行結(jié)果：

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

以下是參考LeetCode中使用STL實現(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]

要求時間復(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)行部分代碼修改實現(xiàn)成功的程序

運行結(jié)果：

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

以下是參考LeetCode中實現(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;
	}
};

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享標(biāo)題：數(shù)組——RemoveDuplicatesfromSortedArray-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://www.muchs.cn/article6/ceocog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營銷、品牌網(wǎng)站設(shè)計、品牌網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、動態(tài)網(wǎng)站、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)