Google : 找出第一个只出现一次的字符

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

先写个最直接的。

开两个int数组。扫描字符串，一个记录字符出现的次数，一个记录字符第一次出现的位置。
扫描字符串后，把两个int数组扫描一遍，就可以知道答案了。
效率O(256+N)。

回复 2# ljfljf2006
好像也想不出更好的了。。

回复 4# holyzz
大体上是这样没错，但带着常数考虑的话，你说的这个方法需要扫描两遍，是2n，2楼的方法是n+256，在n比较大的时候还是更优一些。关键在于第二遍再扫描原数组的话可能有许多重复操作是无效的。不过如果字符是unicode编码的话，就不止256种情况了。不知还有没有更好的办法

回复  holyzz
大体上是这样没错，但带着常数考虑的话，你说的这个方法需要扫描两遍，是2n，2楼的方法是n+256，在n比较大的时候还是更优一些。关键在于第二遍再扫描原数组的话可能有许多重复操作是无效的。不过如果字符是unicode编码的话，就不止256种情况了。不知还有没有更好的办法
darksteel 发表于 2011-5-17 09:03

不是的，holyzz的解法时间复杂度是O(n),空间复杂度是O(1),因为256是常量，O(256n) == O(n)
O(256) = O(1),

回复 6# wwwyhx
空间的256可以算是O(1)。时间上是O(n)肯定没错，不过这个过程比较单一的用渐进复杂度就不合适了，我只是想说明上面的解法是2n，2楼的解法是n+256，两者稍有点区别

回复  holyzz
大体上是这样没错，但带着常数考虑的话，你说的这个方法需要扫描两遍，是2n，2楼的方法是n+256，在n比较大的时候还是更优一些。关键在于第二遍再扫描原数组的话可能有许多重复操作是无效的。不过如果字符是unicode编码的话，就不止256种情况了。不知还有没有更好的办法
darksteel 发表于 2011-5-17 09:03

    的确更简洁一些，解释一下，两个数组A[256]和B[256],A是letter->time,B是order->letter, 相当于两个映射表。记录order就是为了快速的定位到下一个只出现一个的元素，good!!

char GetFirstOnce(const char* szString)
{
        assert(NULL != szString);

        int ChrToFreq[256];
        memset(ChrToFreq, 0, sizeof(ChrToFreq));
        char OrderToChr[256];
        memset(OrderToChr, 0, sizeof(OrderToChr));

        int nIter = 0;
        int nRet = 0;
        while (0 != *szString)
        {
                ChrToFreq[*szString]++;
                if (1 == ChrToFreq[*szString])
                        OrderToChr[nIter++] = *szString;
               
                while(nRet < nIter && ChrToFreq[OrderToChr[nRet]] > 1) nRet++;

                szString++;
        }

        if (nRet == nIter) return 0;

        return OrderToChr[nRet];
}

从后往前扫描，如果该字符无重复hash值，不就只要扫描一遍了么？