查找字符串中第一个只出现一次的字符

现在的位置: 首页 > 综合 > 正文

查找字符串中第一个只出现一次的字符

2013年10月09日 ⁄ 综合 ⁄ 共 1041字 ⁄ 字号小中大 ⁄ 评论关闭

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

分析：如果字符都是8位，可以用256B的空间表示每个字符的出现次数，遍历字符串一遍完成计数，第二次遍历该字符串，找出第一个出现次数仅为1的字符并输出。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
void get_rand_str(char s[],int number)
{
        char str[64] = "00123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 
        int i;

        srand((unsigned int)time((time_t *)NULL));
        for(i=0;i < number-1;i++){
               s[i] = str[(rand()%62)+1];
        }
        s[i] = '\0';
        printf("%s\n",s);
}

char FirstNotRepeatingChar(char* pString)
{
	int hashtable[256];
	memset(hashtable, 0, sizeof(int)*256);
	
	char *pstr = pString;
	while (*pstr != '\0')
		hashtable[*pstr++]++;
	
	pstr = pString;
	while (*pstr != '\0')
	{
		if (1 == hashtable[*pstr])
			break;
		pstr++;
	}
	return *pstr;
}

int main()
{
	char str[120];
	get_rand_str(str, 120);
	printf("the first :%c\n",FirstNotRepeatingChar(str));
}

扩展：如果这里的字符换成64位的整数，并且这里的整数数量为几十TB甚至更多呢？

Hash的方法变成不可能，因为没有这么大的内存。二这里又是海量的数据，要尽可能避免读写外存数据。

分析：这里只为大家介绍一种排序的思路，欢迎大家提供更好的思路。总的数据量为N，假设内存最多能为n个整数排序，那么外存中的数据可以被分为M=N/n个块。