关于删除数组中的重复元素，纠结死了

本来以为是很简单的问题，没想到让我搞了大半天！本来想只用一个数组解决的，谁知道鼓捣了半天也没成功（其实功能是有的，但是操作数莫名其妙地高，无法理解之下，就用了这个新版本），于是弄了一个新版本，就是用两个数组来解决。下面的这个是我的delete_repeat函数的定义部分，其中s[]是要进行操作的数组，而number_used是该数组的实际维数，因为操作之后维数可能会减少，所以用了call-by-reference类型。

这个版本还算是比较清晰的，不过我也是搞了很久才弄成这样的。我的问题是：
1、在仅仅使用<iostream>的前提下，怎么定义delete_repeat函数最清晰且不容易出错？

2、在仅仅使用<iostream>的前提下，怎么定义这个函数能够让运行效率最高（至少比这个高）？

注意：这个函数不能打乱原数组中元素的顺序！

void delete_repeat(char s[], int& number_used)
{
	int dimension = number_used; // dimension是数组t[]的实际维数
	char t[MAX_DIM];
	for(int i =0; i != dimension; ++i)// 将数组s[]中的元素复制到t[]中，并将s[]“清零”
	{
		t[i]=s[i];
		s[i]='\0';
	}
	int i=0, j=0; // i是数组t[]的下标，而j是数组s[]的下标
	while(i!=dimension)
	{					 
		// 在给s[j]赋值之前，先检查t[i]是否与s[j]前面的元素有重复
		bool repeat = false;
		for(int k=0; k<j; ++k)
		{
			if(t[i]==s[k])
			{
				repeat = true;
				// 如果有重复，那么将i往右移一位
				++i;
				break;
			}
		}
		if(repeat == false) // 没有重复的话，那么s[j]的值就是t[i]了，此时将i增加一位
		{
			s[j]=t[i];
			++j;
			++i;
		}
	}
	number_used = j;
}

13 个解决方案

#1

这还要怎么折腾，用双链表最好了。
定义两个指针front,tail，同时指向数组首尾，tail开始向前移动，与首front的值进行比较：

   if(*tail == *front) 删掉tail，然后再往前移动，直到 tail = front 进行下一轮;

直到front为null就结束，表示删除完毕！

#2

来个人支持吧

#3

看lz的函数原型，目标数组是char类型的呀？char的表示范围是-128~127，用hash吧，方便，仅供参考：

void delete_repeat(char s[], int& number_used)
{
    char already_in_s[256] = {0}, c;
    int len = 0, i;
    
    for(i = 0; i < number_used; ++i){
        c = s[i] < 0 ? 256 + s[i] : s[i];
        if(!already_in_s[c]){
            s[len++] = c;
            already_in_s[c] = 1;
        }
    }
    number_used = len;
}

#4

void delete_repeat(char s[], int &number_used)
{
	int pos =0,i,j;
	for(i =0; i< number_used; i++){
		for(j =0; j< i; j++){
			if(s[i] == s[j]){
				break;
			}
		}
		if(i == j){
			s[pos++] = s[i];
		}
	}
	s[pos]='\0';
	number_used = pos;
}

还是喜欢这样，空间也没浪费

#5

http://www.cplusplus.com/reference/algorithm/unique/

#6

引用 5 楼 zhao4zhong1 的回复:

http://www.cplusplus.com/reference/algorithm/unique/

有木有中文版呀？英文版虽然也能看，但是看着费劲。

#7

仅仅使用iostream的话，你就需要找本《stl源码剖析》，抄抄stl里的*：sort+unique

#8

char s[] = {...} //反正就是初始化啦，里面塞一堆数据
std::unique(s, s+sizeof(s)/sizeof(char)); //重复元素删除完成~

里面的s可以换成任何支持前向迭代器的容器，不论是stl，还是你自己造，或者其他一些库里面的。当然容器的元素得能判断相等。

#9

排序完不就容易去冗了？数组要保持原顺序没关系啊，对index排序不就结了？

#include <iostream>
#include <algorithm>
#include <vector>

char testA[]="This is a random string and I am going to remove all but the very"
	" first occurance of any characters contained.";

void delete_repeat(char s[], int& count)
{
	std::vector<int> indexes;
	indexes.reserve(count);
	for(int i=0; i<count; ++i)
		indexes.push_back(i);
	std::stable_sort(indexes.begin(), indexes.end(), [s](int i, int j){	return s[i]<s[j];});
	auto end=std::unique(indexes.begin(), indexes.end(), [s](int i, int j){return s[i]==s[j];});
	std::sort(indexes.begin(), end);
	for(int i=0; i<indexes.size(); ++i)
		printf("%d\n", indexes[i]);
	int j=0;
	for(auto i=indexes.begin(); i<end; ++i)
		s[j++]=s[*i];
	count=end-indexes.begin();
}



int main(int argc, const char *argv[])
{
	int cnt=sizeof(testA)-1;

	delete_repeat(testA, cnt);
	testA[cnt]='\0';
	std::cout<<testA<<endl;

	return 0;
}

#10

O(N)的采用计数机制，类似基数排序
记录每个字符，第一次出现的时候，记录到另一个表里。

#11

bieset<256>  

#12

学习下，楼主用的方法好像比较死

#13

我了去，这都写不出来