如何在一个字符串中查找第一个不重复的字母

如何在一个字符串中查找第一个不重复的字母？
例如：“instantiation” 字符串中，第一个不重复的字母是“s”
最好有代码，谢谢各位

23 个解决方案

#1

#include <stdio.h>
#include <stdlib.h>

void search(char *S, char *c)
{
	int i, j, k;
	for(i=0; S[i]!='\0'; i++) 
	{
		k = 0;
		for(j=0; S[j]!='\0'; j++) 
		{
			if(i == j)
				continue;
			if(S[i] == S[j]) 
			{
				k++;
				break;
			}
		}
		if(k == 0) {
			*c = S[i];
			return;
		}
	}
}

void main()
{
	char s[50] = "instantiation", c;
	search(s, &c);
	printf("字符串 %s 中第一个不重复的字符是：%c \n", s, c);
}

#2

1楼的复杂度是O(n^2)，算法太不好了

扫描两遍就可以了，算法复杂度是O(n)


int search(char *S)
{

int pos = -1;  // 缺省设为-1
unsigned char flag[256];  // 记录字符出现的次数
memset(flag, 0, 256);


for(i=0; S[i]!='\0'; ++i)
{
++flag[S[i]];
if (flag[S[i]] > 1) flag[S[i]] = 2; //有重复，超过一次均记为2，防止溢出
}

for(i=0; S[i]!='\0'; ++i)
{
if (flag[S[i]] == 1) // 仅出现一次
{
pos = i; // 返回位置
break;
}
}

return pos;
}

#3

加了一行，防止下标为负

int search(char *Str)
{

	int pos = -1;
	unsigned char flag[256];
unsigned char * S = reinterpret_cast<unsigned char *>(Str);
	memset(flag, 0, 256);


	for(i=0; S[i]!='\0'; ++i)
	{
		++flag[S[i]];
		if (flag[S[i]] > 1) flag[S[i]] = 2;	
	}

	for(i=0; S[i]!='\0'; ++i)
	{
		if (flag[S[i]] == 1) 
		{
			pos = i; 
			break;
		}
	}

	return pos;
}

#4

二楼一次循环后flag[]都为1了

#5

反向扫描一遍即可，修改自3楼

char search(char*Str)
{
    unsigned char flag[256];
    unsigned char*S=reinterpret_cast<unsigned char*>(Str);
    memset(flag,0,256);
   int nLen=strlen(str);
  char result=0;
  for(i=0; i<nLen;++i)
    {
   ++flag[S[i]];
    if(flag[S[i]]==1)
    result=S[i];
   else if(flag[S[i]]==2){
     if(result==S[i])
        result=0;
   }
   else 
     flag[S[i]]=3;  
     }
   return result;
}

#6

for循环忘了改过来,另貌似strlen()也要遍历一遍
for(int i=nLen-1; i>-1;i--)

#7

遍历2次
一个统计字母出现的个数
一个查找统计数组中的1个, 找到就返回

#include "stdafx.h"
#include <iostream>

char testFunction (char* pszText)
{
	// first run, count letters using in the string		

	int set[256];
	memset (set,0, sizeof(set));
	for (int i=0;i<strlen(pszText);i++)
		++set[pszText[i]];
	for (int i=0;i<strlen(pszText);i++)
	{
		if (set[pszText[i]] == 1)
		{
			//find it and break;
			return pszText[i];
		}
	}
}


int main (void)
{
	std::cout<< "first not repeated letter is "<<testFunction ("instantiation")<<std::endl; 
	system ("pause");
}

#8

学习了

#9

引用 7 楼 hhygcy 的回复:

遍历2次
一个统计字母出现的个数
一个查找统计数组中的1个, 找到就返回

C/C++ code#include"stdafx.h"#include<iostream>chartestFunction (char*pszText)
{//first run, count letters using in the stringintset[256];
    memset (set,0,sizeof(set));for(inti=0;i<strlen(pszText);i++)++set[pszText[i]];for(inti=0;i<strlen(pszText);i++)
    {if(set[pszText[i]]==1)
        {//find it and break;returnpszText[i…

三个bug：

1.  ++set[pszText[i]] 虽说串长度大于2^32的可能性不大，但是最好加上机制防止溢出
2.  ++set[pszText[i]] 中，如果输入字符串是nuicode，数组下标会为负
3， 如果输入数组没有字符仅出现一次，例如“aaaaa”，函数无返回。事实上会返回EAX，将是不确定数

#10

引用 4 楼 mengde007 的回复:

二楼一次循环后flag[]都为1了

请仔细读代码，flag[]下标是S[i]

#11

引用 6 楼 bottlebox 的回复:

for循环忘了改过来,另貌似strlen()也要遍历一遍
for(int i=nLen-1; i>-1;i--)

：）
理论上无论是1N还是2N没有本质区别，复杂度都是O(N)
不过你的想法不错。
不如咱还是从头开始扫描，代码中的
unsigned char flag[256]；
改成 
struct pair
{
 unsigned char flag;
 int pos;
}
pair c_pos[256]；

扫描时若发现flag为1，表明该字符第一次出现，就记录当前位置
扫描结束后，只需扫描结构数组即可，找到flag为1的最小pos值。
这样循环次数是N+C，C指常数，本例中是256，稍稍好过2N


是啊，所以还是直接正序找串结尾好些
第一遍扫描

#12

mmmmmmmmmm

#13

防止溢出毫无意义，如果你定义计数器为int，溢出的唯一可能是字符串长度超过2^32，这是绝对步可能的，因此直接自加是最优算法，没有必要防止溢出

#14

引用 9 楼 xxjjs 的回复:

引用 7 楼 hhygcy 的回复:
遍历2次
一个统计字母出现的个数
一个查找统计数组中的1个, 找到就返回

C/C++ code#include"stdafx.h"#include <iostream>chartestFunction (char*pszText)
{//first run, count letters using in the stringintset[256];
memset (set,0,sizeof(set));for(inti=0;i <strlen(pszText);i++)++set[pszText[i]];for(inti=0;i <strlen(pszText);i++)
{if(set[pszText[i]]==1)
{//find it and brea…

呵呵 其实我觉得, 来求代码的同学都求不到最好的代码
关键的是明白一个大意, 想法, 如果全部的东西都得到了 就少了自己思考的过程, 印象不深了(开玩笑的)
代码是一次性写的, 运行成功就贴出来了, 不妥的地方见谅了

#15

mark

#16

就是一个构建HashTable的方法：
遍历字符串{
  HashTable--元素（KEY ,STRING）
  如果已经有此元素，就删除掉
}
遍历第二次字符串搜索HashTable,找见的就是了！

#17

以前讨论过，O(n)就可以，LZ可以搜索一下相关帖子！

#18

        private static char findChar(string chars)
        {
            char value = ' ';
            if (chars != null && chars.Length != 0)
            {
                int count = 0, index = -1;
                long bits = 0, deleteBits = 0, andValue;
                long[] valueArray = new long[52];
                char[] charArray = new char[52];
                foreach (char c in chars)
                {
                    if ((andValue = (c >= 'a' || c <= 'z' ? (1L << (c - 'a')) : (c >= 'A' || c <= 'Z' ? (1L << ((c - 'a') + 32)) : 0))) != 0)
                    {
                        if ((bits & andValue) == 0)
                        {
                            bits |= andValue;
                            valueArray[++index] = andValue;
                            charArray[index] = c;
                        }
                        else
                        {
                            deleteBits |= andValue;
                            if ((++count) == 52) break;
                        }
                    }
                }
                if (count != 52 && index != -1)
                {
                    for (count = 0; count <= index && (deleteBits & valueArray[count]) != 0; count++) ;
                    if (count <= index) value = charArray[count];
                }
            }
            return value;
        }

#19

public class SearchFirstUniqueChar {
	public static void main(String[] args) {
		String string = "instantiation";
		char c = searchFirstUniqueChar(string);
		if (c != 0) {
			System.out.println(String.format("The char is :%s", c));
		}else {
			System.out.println(String.format("No unique char"));
		}
	}

	private static char searchFirstUniqueChar(String string) {
		for (int i = 0; i < string.length(); i++) {
			char c = string.charAt(i);
			int lastIndexOf = string.lastIndexOf(c);
			if (lastIndexOf == i) {
				return c;
			}
			//可加缓存保留已经检测过的支付，但是对小规模字符串无意义
		}
		return 0;
	}

}

#20

我的思路跟3，5楼的相同

#21

就是一个26个字母数组，不过要保存一下出现字母的顺序。。。。。

#22

由于是字符串，只有26个字母，可以用一个int map[26]的位图来统计就可以了。
遍历一次，然后就有结果了。

#23

顶二楼的！
多么漂亮的算法啊 ！
不知道那几位朋友怎么看人家的算法的……