字符数组里的成双成对

柔情只为你懂 2022-08-21 12:40 57阅读 0赞

# 查找字符串中第一个只出现一次的字符，要求复杂度为:O(n) #

首先先给出代码的测试部分：

int main()
    {
    	char ret=0;
    	int sz=0;
    	char str[20];
    	printf("请输入你要查找的字符串:");
    	gets(str);
    	sz=strlen(str);
    	ret=seek_one(str,sz);
    	printf("第一个只出现一次的字符是:%c\n",ret);
    	system("pause");
    	return 0;
    }

方法一:

【问题分析】

拿到这样的一道题，我首先想到的是先遍历整个字符串，在遍历的过程中，再将该字符与后面的字符比较，并设置标志位，如果字符后面存在和该字符相等的字符就将标志位设置为1，如果没有(flag == 0)则说明该字符只出现了一次，就返回此字符,返回的字符就是我们要查找的第一个出现一次的字符。下面我们就来实现这种思路:

char seek_one(char *str,int sz)
    {
    	int i=0;
    	int j=0;
    	int flag=0;
    	for(i=0;i<sz;i++)
    	{
    		flag=0;  //说明字符只出现一次
    		for(j=i+1;j<sz;j++)
    		{
    			if(str[i] == str[j])
    			{
    				flag=1; break; //说明有重复出现的字符
    			}
    		}
    		if(flag == 0)
    			return str[i];
    	}
    	return 0;
    }

【实验结果】

![Center][]

【代码缺陷】

这种查找方式存在缺陷，我们知道这种方式的思路是先遍历整个字符串，在遍历的过程中又再次遍历此字符之后的字符进行查找是否该字符出现过两次或者两次以上，它的时间复杂度是:O(n^n),使得字符匹配效率不高，延迟了匹配时间。

代码优化:

方法二：

【问题分析】

我们先来给出程序的测试代码:

int main()
    {
    	char ret=0;
    	char arr[20];
    	printf("请输入你要查找的字符串:");
    	gets(arr);
    	ret=check_one(arr);
    	if(ret != 0)
    	{
    		printf("第一个只出现一次的字符是:%c\n",ret);
    	}
    	system("pause");
    	return 0;
    }

如果我们不使用方式一，那仫我们应该如何解决问题呢？如果我们能用一个足够大的数组来记录每个字符出现的次数，在程序的最后如果我们只要遍历这个数组找到对应的字符出现的个数是1，那仫我们就返回出现个数是1的字符否则就继续查找。下面我们就来实现这种思路:

char check_one(char *arr)
    {
    	char *ptr=arr;
    	int hash[300]={0};
    	assert(arr);
    	while(*ptr != '\0')   //第一次遍历字符串记录字符出现的次数
    	{
    		hash[*(ptr++)]++;
    	}
    	ptr=arr;
    	while(*ptr != '\0')  //第二次遍历找出字符出现次数是1的字符
    	{
    		if(hash[*ptr] == 1)
    		{
    			return *ptr;
    		}
    		else
    		{
    			ptr++;
    		}
    	}
    	return 0;
    }

【实验结果】

![Center 1][]

【算法评价】

我们以字符串"aaaabfqccrbddw"为例，它在内存中的对应关系为：

![Center 2][]

我们可以知道的是对于字符数组arr\[\]和整形数组hash\[\]而言他们被都遍历过，他们的时间复杂度都是o(n),字符数组的时间复杂度o(n)比第一种方法o(n^n)小。

【课外小知识】

上述第二种方法其实利用了数据结构中的一种结构，叫散列表又名哈希表：是在记录的存储位置和它的关键字之间建立了一种确定的对应关系f，就像是在整形数组hash\[\]中可以找到字符数组arr\[\]中对应字符出现的个数;

散列函数（哈希函数）：就是这种对应关系f

散列表（哈希表）：将记录存储在一块连续的空间中，这块连续的存储空间就叫做散列表（哈希表）。

散列技术即是一种存储方式，也是一种查找方法；就像是在hash\[\]数组中用来查找字符出现的个数为1一样；

但是需要注意的是：散列技术的记录之间不存在什仫逻辑关系，它只与关键字有关；就像是我们在hash\[\]数组中可以找到arr\[\]数组中字符出现的个数一样，但是hash\[\]中的数据之间并没有什仫必然联系，只与arr\[\]数据中的对应字符有着联系。

好了对于散列表的介绍仅限于此，以后学到数据结构的时候会做更加详细的理解。以上就是我个人对“查找一个字符串中第一个只出现一个字符的认识”问题的认识，如果有什仫需要优化和改进的地方请大家指出。

[Center]: /images/20220724/38455965470b474db437bb1499fbbe80.png
[Center 1]: /images/20220724/43c27b80d96c416aa0b6ea74da037228.png
[Center 2]: /images/20220724/faf4db8ba3624c469de87d2eb1a6afeb.png