讨论算法：字符串中找到第一个只出现一次的字符

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

29 个解决方案

#1

既然只出现一次，也就没有所谓“第一个”了。

#2

string str = "abaccdeff";
        string rs = string.Empty;
        foreach (char s in str)
        {
            string[] arg = str.Split(s);
            if (arg.Length == 1)
            {
                return rs = s.ToString();
                break;
            }
        }

#3

一个开销在n~2 ，但是如果先排序的话，可能会快一点，也可以在排序中计算出第一个来

#4

扫描两次字符串就可以了.
第一趟给所有字母计数.
第二趟找第一个次数为1的字母

#5

引用楼主 likee003 的回复:

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

字符串这个东东，用位图是再好不过了。

#6

int main() 
{ 
	char c[]="abaccdeff";
	int bit_map[26]={0};
	int i=0;
	for(;i<strlen(c);++i)
			bit_map[c[i]-'a']++;
	for(i=0;i<strlen(c);++i)
	{
		if(bit_map[c[i]-'a']==1)
		{
			printf(" %c ",c[i]);
			break;
		}
	}
	if(i>=strlen(c))
		printf("No ele to the rule\n"); 
	return 0;
} 

位图实现，O(n)的时间复杂度跟O(1)的空间复杂度。

#7

引用 6 楼 hairetz 的回复:

C/C++ codeint main() 
{char c[]="abaccdeff";int bit_map[26]={0};int i=0;for(;i<strlen(c);++i)
            bit_map[c[i]-'a']++;for(i=0;i<strlen(c);++i)
    {if(bit_map[c[i]-'a']==1)
        {
            printf(" %c",c[i]);break;
        }
    }if(i>=strlen(c))
        printf("No ele to the rule\n");return0;
}

位图实现，O(n)的时间复杂度跟O(1)的空间复杂度。

学习了，原来这个叫位图。

#8

挑下骨头：strlen(c)，每执行一次，就是O(n)，总体算法时间复杂度就变成了O(n^2)。。

引用 6 楼 hairetz 的回复:

C/C++ codeint main() 
{char c[]="abaccdeff";int bit_map[26]={0};int i=0;for(;i<strlen(c);++i)
            bit_map[c[i]-'a']++;for(i=0;i<strlen(c);++i)
    {if(bit_map[c[i]-'a']==1)
        {
            printf(" %c",c[i]);break;
        }
    }if(i>=strlen(c))
        printf("No ele to the rule\n");return0;
}

 位图实现，O(n)的时间复杂度跟O(1)的空间复杂度。

#9

引用 1 楼 gamedragon 的回复:

既然只出现一次，也就没有所谓“第一个”了。

有N个只出现一次的字母，只取第一个。

#10

strlen(c)应该是O(1)的，所以总共是O(n)的！

这类问题用C# linq来做很有意思（写的不太简洁，不过是这个意思）。也是O(n)的。

using System;
using System.Linq;

namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            string test = "abaccdeff";
            var g = (from item in test group item by item into groups where groups.Count() == 1 select groups).First();
            Console.WriteLine(g.Key);
        }
    }
}

引用 8 楼 m_s_d_n 的回复:

挑下骨头：strlen(c)，每执行一次，就是O(n)，总体算法时间复杂度就变成了O(n^2)。。

#11

该回复于2010-01-06 15:50:44被版主删除

#12

size_t __cdecl strlen (
        const char * str
        )
{
        const char *eos = str;

        while( *eos++ ) ;

        return( (int)(eos - str - 1) );
}

这个函数时间复杂度是O(1)？

引用 10 楼 litaoye 的回复:

strlen(c)应该是O(1)的，所以总共是O(n)的！

 这类问题用C# linq来做很有意思（写的不太简洁，不过是这个意思）。也是O(n)的。

 using System;
 using System.Linq;

 namespace ConsoleApplication4
 {
     class Program
     {
         static void Main(string[] args)
         {
             string test = "abaccdeff";
             var g = (from item in test group item by item into groups where groups.Count() == 1 select groups).First();
             Console.WriteLine(g.Key);
         }
     }
 }

引用 8 楼 m_s_d_n 的回复:
 挑下骨头：strlen(c)，每执行一次，就是O(n)，总体算法时间复杂度就变成了O(n^2)。。

#13

这是strlen的原型么？如果是这样的话确实不是O(1)。不好意思啦，C的函数不熟呀！
不过总感觉不太可能，求个字符长度会用这种方法？

引用 12 楼 m_s_d_n 的回复:

size_t __cdecl strlen (
         const char * str
         )
 {
         const char *eos = str;

         while( *eos++ ) ;

         return( (int)(eos - str - 1) );
 }

#14

btw，即使strlen是O(n)的，#6楼的程序应该也还是O(n)的！

#15

不好意思，这个还真不一定。回头试验一下吧！

引用 14 楼 litaoye 的回复:

btw，即使strlen是O(n)的，#6楼的程序应该也还是O(n)的！

#16

即使不是原型，也肯定不是O(1)，因为根本不存在O(1)的算法。

引用 13 楼 litaoye 的回复:

这是strlen的原型么？如果是这样的话确实不是O(1)。不好意思啦，C的函数不熟呀！
 不过总感觉不太可能，求个字符长度会用这种方法？

引用 12 楼 m_s_d_n 的回复:
 size_t __cdecl strlen (
          const char * str
          )
  {
          const char *eos = str;

          while( *eos++ ) ;

          return( (int)(eos - str - 1) );
  }

#17

.Net里面就是O(1)，头尾一减就行了。

引用 16 楼 m_s_d_n 的回复:

即使不是原型，也肯定不是O(1)，因为根本不存在O(1)的算法。

#18

  遍历两次，肯定可以找到.
  char fun(char *str,int n)
  {
      //开数组 num,初始化0
      //第一次遍历.
      for(int i = 0;i<n;i++)
            num[str[i]-'a']++;
     //第二次遍历
       for(int i = 0;i<n;i++)
            if(num[str[i]-'a'] == 1)  return str[i];
     //如果没有，自己返回个ooxx符号吧  
  }
  
  有没有遍历一次的算法？

#19

引用 17 楼 litaoye 的回复:

.Net里面就是O(1)，头尾一减就行了。

引用 16 楼 m_s_d_n 的回复:
即使不是原型，也肯定不是O(1)，因为根本不存在O(1)的算法。

那也是构造的时候要数一遍。

从纯粹strlen的角度看，对待未知长度的string就是要O(n)的时间复杂度。

#20

晕，回一次贴，大家这么纠结。

直接声明一个int len = strlen(c);得了。

我之前是偷懒，写快了，就懒得声明。

其实不管编译器里是否有优化，这样声明一个总是不亏的。

#21

  有没有遍历一次的算法？

#22

引用 21 楼 longteng1116 的回复:

有没有遍历一次的算法？

不错，大家都沉迷于mathe的两次遍历算法的时候，你指明了一个新路。
可以用一个数组建立字母出现顺序表，然后按这个顺序表找统计表里为1的就行了。

#23

引用 22 楼 gogdizzy 的回复:

引用 21 楼 longteng1116 的回复:
有没有遍历一次的算法？


不错，大家都沉迷于mathe的两次遍历算法的时候，你指明了一个新路。
可以用一个数组建立字母出现顺序表，然后按这个顺序表找统计表里为1的就行了。

其实你生成+查找，还是2次的。


只有O(n)，常数级的差异不用太在意吧。

#24

引用 23 楼 hairetz 的回复:

   ..............

  有个研究生考试题目：给定一个带头指针的链表(长度大于N），让你设计算法找到倒数第N个。
  遍历两次找到：<10分；
  遍历一次找到：15分；
  你说有区别么？  
  O(2n)和O（n)虽然在实现效率上都是O(n),但是思路上的启发就不一样了。

#25

主要是2遍和1遍效率其实是差不多的，一摸一样的问题以前讨论过，就是记录一下第一个出现的位置，
可实现一次遍历。

BTW，别小看C#的linq，其实是遍历1遍的

引用 22 楼 gogdizzy 的回复:

引用 21 楼 longteng1116 的回复:
 有没有遍历一次的算法？


 不错，大家都沉迷于mathe的两次遍历算法的时候，你指明了一个新路。
 可以用一个数组建立字母出现顺序表，然后按这个顺序表找统计表里为1的就行了。

#26

只要多做点工作就可以遍历一次吧？
遍历的过程中始终记录目前为止只出现一次的第一个字母，并且做一个链表把下一个记住，不难实现。

#27

引用 23 楼 hairetz 的回复:

引用 22 楼 gogdizzy 的回复:
引用 21 楼 longteng1116 的回复:
有没有遍历一次的算法？


不错，大家都沉迷于mathe的两次遍历算法的时候，你指明了一个新路。
可以用一个数组建立字母出现顺序表，然后按这个顺序表找统计表里为1的就行了。


其实你生成+查找，还是2次的。


只有O(n)，常数级的差异不用太在意吧。

其实你的算法，如果第一个只出现一次的字符是等概率的话，那平均复杂度是1.5n，第二次遍历平均长度是n/2。
而如果我构造一个出现顺序表，似乎必须要花2n的时间，因为要在统计表增加之前判断是否出现过。所以可能我这个方法效率不一定高，如果非要给自己找个理由，可能就是当数据量很大，存储在硬盘里，读两次可能更费时间吧。

我认为，常数级的差异，如果体现在代码实现上，可以忽略，因为毕竟不是所有人都是高手，但是如果体现在算法上，还是有意义的。一个程序员说：对一个人来说1ms和50ms可能没什么差异，但是1天和50天绝对不是一回事。

#28

以下代码仅供参考，输入只能为小写字母串，否则会数组越界。

char checkText( char* strText )
{
	int i, count[26], *cnt = count - int('a'), pos = 0;
	char appear[26], *apr = appear - int('a'), c, *pStr = strText;
	memset( count, 0, sizeof(count) );
	memset( appear, 0, sizeof(appear) );
	for( ; c = *pStr; pStr++ ) //遍历一遍字符串数组
	{
		cnt[c] || (appear[pos++] = c); // if( !cnt[c] )，这里多了判断，所以变成了2n
		cnt[c]++;
	}

	for( i = 0; i < pos; i++ ) // 共出现了pos个字符，在appear数组中顺序出现，pos<=26，
	{                          // 所以复杂度为常量。
		if( 1 == cnt[appear[i]] ) return appear[i];
	}
	return '\0';
}

#29

public class Abaccdeff{
		public static void main(String[] arg) {
				if (arg.length==0) arg = new String[]{"abaccdeff"};
				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();
		}
}