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

描述

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

要求時間復雜度為O（n）,空間復雜度為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為第一個元素下標，second為第二個元素下標（如果數(shù)組只有一個元素，則不會進入循環(huán)，而是直接返回1）

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

運行結果：

測試數(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]

要求時間復雜度為O（n）,空間復雜度為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進行部分代碼修改實現(xiàn)成功的程序

運行結果：

測試數(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;
	}
};

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

分享標題：數(shù)組——RemoveDuplicatesfromSortedArray-創(chuàng)新互聯(lián)
網站網址：http://bm7419.com/article6/ceocog.html

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

廣告

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