一道面试题：从一个字符串中找出第一个不重复字符

anjgao 2009-05-13 12:02:00

加精

比如：
abbbccdefafgg 其中d、e只出现一次，只需要找出d(第一个出现的不重复字符)即可

有什么最快的方法？

...全文

6715 122 打赏收藏转发到动态举报

写回复

用AI写文章

122 条回复

切换为时间正序

请发表友善的回复…

发表回复

zhongshch 2010-07-12

打赏
举报

[Quote=引用 26 楼 liao05050075 的回复:]
引用 11 楼 xwb2766 的回复:
4楼 liao05050075 的还有bug

可以用
char *s="agaabbbcccsdddefffg";
测试
结果是：e 而不是 s

-_-|||||
ai....真是SB了我。。写个小程序错漏百出。。真是没得救了。。。抱歉啊。。。
这回总该OK了吧。。

C/C++ code

#include<stdio……
[/Quote]
似乎还是有问题，如果字符串是char *s="agaabbbcccdddfffg"; 会输出'a'。

土豆吞噬者 2010-06-09

打赏
举报



function getchar(s:string):char;

var

 i,j:integer;

 a:string;  //重复的字符

 b:string;  //不重复的字符

 mbool:Boolean;

begin

 a:='';

 b:='';

 for i:=1 to length(s)do

 begin

   mbool:=False;

   for j := 1 to Length(b) do

   begin

     if b[j] = s[i] then //加入到重复字符中

     begin

       mbool:=True;

       Delete(b,j,1);

       SetLength(b,length(a)+1);

       a[length(a)]:= s[i];

     end;

   end;

   if mbool = False then  //没有重复

   begin

     for j := 1 to length(a) do

     begin

       if a[j]  = s[i] then //已经在重复数组中

       begin

         mBool:=True;

         Break;

       end;

     end;

   end;

   if mbool = False then //不在重复列表中 加入不重复列表

   begin

     SetLength(b,length(b)+1);

     b[length(b)]:= s[i];

   end;

 end;

 if Length(b)>=1 then Result:=b[1];

end;

土豆吞噬者 2010-06-09

打赏
举报

function getchar(s:string):char;
var
i,j:integer;
a:string; //重复的字符
b:string; //不重复的字符
mbool:Boolean;
begin
a:='';
b:='';
for i:=1 to length(s)do
begin
mbool:=False;
for j := 1 to Length(b) do
begin
if b[j] = s[i] then //加入到重复字符中
begin
mbool:=True;
Delete(b,j,1);
SetLength(b,length(a)+1);
a[length(a)]:= s[i];
end;
end;
if mbool = False then //没有重复
begin
for j := 1 to length(a) do
begin
if a[j] = s[i] then //已经在重复数组中
begin
mBool:=True;
Break;
end;
end;
end;
if mbool = False then //不在重复列表中加入不重复列表
begin
SetLength(b,length(b)+1);
b[length(b)]:= s[i];
end;
end;
if Length(b)>=1 then Result:=b[1];
end;

jdtxse 2010-05-18

打赏
举报

学习了。

真的吗咚咚 2010-05-18

打赏
举报

如果只考虑26个字母的情况的话，对26楼代码做了一点点优化：
#include <stdio.h>
#include <string.h>

#define MAX_LETTER_NUM 26

int main(void)
{
unsigned char num[MAX_LETTER_NUM] = {0}, index[MAX_LETTER_NUM] = {0};
unsigned char *str = "ajdfjosiuia";
int i, len = strlen(str), n = 0, first = len;

for(i = 0; i < len; i++)
{
n = str[i] - 'a';
num[n]++;
index[n] = i;
}

for(i = 0; i < MAX_LETTER_NUM; i++)
{
if(!num[i])
{
continue;
}
if((num[i] == 1) && (index[i] < first))
{
first = index[i];
}
}
printf("the first char which is not repeated in the string is %c.\n", str[first]);
return 0;
}

真的吗咚咚 2010-05-18

打赏
举报

为什么大家都只考虑都是字母的情况，题目明明是不重复的字符！注意，字符的范围不只是a~z的字母。
所以算法远没有26楼想到那么简单哦。。。

jdtxse 2010-05-13

打赏
举报

[Quote=引用 9 楼 scy251147 的回复:]
C# code

static void Main(string[] args)
{
while (true)
{
Program p = new Program();
Console.WriteLine("Please input the Word:\n"……
[/Quote]写了好多。

Azmrael 2010-05-12

打赏
举报

#include<stdio.h>
#include<string.h>
int num[26]={0};
int index[26]={0};
int main()
{
char *s="agaabbbocccsdddeflffg";
int i;
int min,target;
for(i=0;i<strlen(s);i++)
{
num[s[i]-'a']++;
index[s[i]-'a']=i;
}

min=strlen(s);

for(i=0;i<26;i++)
if(num[i]==1 && index[i]<min)
{
min=index[i];
target = i; //4楼一点点修改就行了
}
printf("%c\n",target+'a');
return 0;
}

liuqing9382 2010-05-05

打赏
举报

java菜鸟，纯粹凑热闹而已

public class Dayananda {

		public static void main(String[] arg) {

				if (arg.length==0) arg = new String[]{"Dayananda"};

				System.out.println(new Dayananda().firstNonRepeatedCharacter(arg[0]));

		}

		char firstNonRepeatedCharacter(String s) {

				char[] ca = s.toLowerCase().toCharArray();

				java.util.Map<Character,Boolean> map = new java.util.LinkedHashMap<Character,Boolean>();

				for(Character c : ca) {

					map.put(c,map.containsKey(c));

				}

				for(java.util.Iterator<java.util.Map.Entry<Character,Boolean>> i=map.entrySet().iterator();i.hasNext();) {

					if (i.next().getValue()) i.remove();

				}

				return map.keySet().iterator().next();

		}

}

或者还有另一种上面已经有人提到过



public class NonRepeatedChar {

	public static void main(String[] args) {

		String str = "daxyananda";

		int[] count = new int[26];

		char[] charArr = str.toLowerCase().toCharArray();

		for (char c : charArr) {

			count[c - 'a']++;

		}

		for (char c : charArr) {

			if (count[c - 'a'] == 1) {

				System.out.println("First Non repeated character is : " + c);

				break;

			}

		}

	}

}

richard_yao 2010-04-01

打赏
举报

[Quote=引用 65 楼 houruifeng 的回复:]

引用 4 楼 liao05050075 的回复:
er..写错了
改一下

C/C++ code
#include<stdio.h>
#include<string.h>
int num[26]={0};
int index[26]={0};
int main()
{
char *s="aaedaa";
int i;
for(i=0;i<strlen(s);i++)
……
[/Quote]

四楼的算法思想很好，字符串和结果数组都只遍历了一遍，比我想的还要高明一点。
不过其中的bug改了半天也没改完，有点说不过去了。

输出结果的部分应该改成这样。
for(i=0;i<26;i++)
if(num[i]==1 && index[i]<min)
{
min=index[i]; //和什么比较当然就用什么来赋值
}
printf("%c\n",s[min]); //只有下标那就从字符串中取比较快了

chensb666 2010-03-29

打赏
举报

Mark

duzhongming 2009-12-10

打赏
举报

31楼不错

daryzhang 2009-11-29

打赏
举报

高手一多就有点昏了。。不知道哪个好了---。。。

whywen_MoJian 2009-10-26

打赏
举报

mark

Hiskoa 2009-10-19

打赏
举报

为什么要用 hash ？

用栈不是最简单的么？？

占用的空间又少遍历一次就得到结果了

wensheng_zh2007 2009-10-18

打赏
举报

#include<stdio.h>

#include<string.h>



char FindFirstOnlyChar(const char* s);

int main()

{

    char *s1="agaabbbcccsdddefffg";

    char *s2="agaabbbcccsdddefff";

    char *s3="agaabbbcccsdddefffgse";

    printf("s1:%c\r\n",FindFirstOnlyChar(s1));

    printf("s2:%c\r\n",FindFirstOnlyChar(s2));

    printf("s3:%c\r\n",FindFirstOnlyChar(s3));

    return 0;        

}

char FindFirstOnlyChar(const char* s)

{

    int num[26]={0};

    int index[26]={0};

    int i,len;

    len = strlen(s);

    for(i=0;i<len;i++)

    {

        num[s[i]-'a']++;

		//记住这个字符第一次出现的位置

		if(0==index[s[i]-'a'])

			index[s[i]-'a']=i;

    }

	

    int pos=len;//用pos记住最早出现一个字符出现的位置

    for(i=0;i<26;i++)

    {

		if(num[i]==1)

		{

			if(pos>index[i])

			{

				pos = index[i];

			}

		}

	}    

	if(len == pos)

	{

		return -1;

	}

	else

	{

		return s[pos];

	}

              

}

weixieming 2009-09-29

打赏
举报

字符不一定只有小写字母，还有大写字母，数字字符，标点字符呢

msaden 2009-05-31

打赏
举报

public class serch {
public char serchchar(String string){
int []count=new int[128];
for(int i=0;i<string.length();i++){
char ch=string.charAt(i);
count[ch]=count[ch]+1;
}
for(int i=0;i<string.length();i++){
char ch=string.charAt(i);
if(count[ch]==1)
return ch;

}

return 0;
}
public static void main(String []Args){
serch mean=new serch();
String string="abbbccdefafgg";
char fistone=mean.serchchar(string);
System.out.println("第一个出现的不重复的字母是："+fistone);
}
}

zxqwxyql 2009-05-25