[已解决]在一个字符串中找到第一个只出现一次的字符（不用字典）

sliang28

爱疯 发表于 2013-9-11 09:51
谢谢82！
我不懂哈希算法，很想认识一下。17楼的语法好理解，但为什么要这样我就不知道了。
以这题来说 ...

随便写了个,不会C的也应该能看懂.

爱疯

转自：http://www.cnblogs.com/liuyubloch/archive/2012/08/25/2655705.html

      看到这道题时，最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较，如果在后面没有发现重复的字符，则该字符就是只出现一次的字符。如果字符串有n个字符，每个字符可能与后面的O(n)个字符相比较，因此这种思路时间复杂度是O(n2)。我们试着去找一个更快的方法。
      由于题目与字符出现的次数相关，我们是不是可以统计每个字符在该字符串中出现的次数？要达到这个目的，我们需要 一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的 数据容器中，哈希表正是这个用途。
      哈希表是一种比较复杂的数据结构。由于比较复杂，STL中没有实现哈希表，因此需要我们自己实现一个。但由于本题的特殊性，我们只需要一个非常简单的哈希表就能满足要求。由于字符（char）是一个长度为8的数据类型，因此总共有可能256 种可能。于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。（并不仅限于英文字符，所以这里要考虑256种可能）。
      我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。





我不明白上面这些分析的意思{:241:}

leolee82

明显是考算法的 随便写的肯定被pass掉
另外，21楼的代码不是C，应该是C#，算法效率也不高。细节上面也可优化，i++写成++i的话就每次循环就会少一个临时对象了

爱疯

leolee82 发表于 2013-9-11 12:00
明显是考算法的 随便写的肯定被pass掉
另外，21楼的代码不是C，应该是C#，算法效率也不高。细节上面也可优 ...

尽管语言不同，但算法都是相通的。如果理解为什么有的算法效率更高，会对解决实例很有帮助。
为此，想借vba语言认识一下，比如这题里哈希算法是怎样作用的。不知是否好解释。

leolee82

爱疯 发表于 2013-9-11 10:53
转自：http://www.cnblogs.com/liuyubloch/archive/2012/08/25/2655705.html

      看到这道题时，最直观 ...

这里只需要能存放65-122(A-z在ASCII码)的数组(arr)就行。如果不区分大小写的话26个元素的数组就行。
这个数组用来统计各字母在s中出现的次数。由于只需统计出来1次的，超过一次的可以计为255（其他不是0和1的数字都行），这样可以减少计数的次数。
其实像下面这样也行，效率不一定会低。因为只是做加法运算，没了条件判断。
For i = 0 To UBound(b)
    arr(b(i)) = arr(b(i)) + 1
Next

leolee82

爱疯 发表于 2013-9-11 12:31
尽管语言不同，但算法都是相通的。如果理解为什么有的算法效率更高，会对解决实例很有帮助。
为此，想借 ...

我的理解，HASH简单的说就是通过简单的算法（f(x)）把集合数据归类,也就是说对于多个x，f(x)的值相同归为一类，每一类作为数组的第f(x)个元素，即arr(f(x))。
这样查找x，就只需要在arr(f(x))这个子集中查找即可.

leolee82

字典也是hash实现的，字典的hash函数f(x)的值的范围是0－1200。下面是VB6中的测试代码

1. Private Sub Form_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)
   
2.     Dim m
   
3.     Dim d As New Dictionary
   
4.     For c = 0 To 10000
   
5.         s = s & Chr(60 + 60 * Rnd)
   
6.         i = d.[HashVal](c)
   
7.         m = IIf(m < i, i, m)
   
8.         If i >= 1200 Then Debug.Print c, vbTab, (i)
   
9.         
   
10.         If d.Exists(i) Then
    
11.             
    
12.         Else
    
13.             d.Add i, 0
    
14.         End If
    
15.         
    
16.         PSet (c, i)
    
17.     Next
    
18.     PSet (3, 3)
    
19.     PSet (3, 4)
    
20.     Line (0, 0)-(100, 100)
    
21. End Sub

复制代码

sliang28

leolee82 发表于 2013-9-11 13:28
这里只需要能存放65-122(A-z在ASCII码)的数组(arr)就行。如果不区分大小写的话26个元素的数组就行。
这个 ...

哈希算法到底是什么东东啊!度娘上一堆文字,看着晕.老师有没有通俗易懂的方法让人明白这个算法{:3912:}

开辆小富康

Sub test()
Const a = "aabcdefffg"
For i = 1 To Len(a)
   If InStrRev(a, Mid(a, i, 1)) = InStr(a, Mid(a, i, 1)) Then
     MsgBox Mid(a, i, 1)
     Exit For
   End If
Next i
End Sub

上面已经有人答了。哈。没仔细看

爱疯

开辆小富康 发表于 2013-9-11 16:10
Sub test()
Const a = "aabcdefffg"
For i = 1 To Len(a)

谢谢小富康！

从解决实际问题角度来说，6楼3种都很实用。而在这几种里，我觉得修改后的“替换”更好，如16#

因为在遇到最糟糕字符串时，形如"aaaaaaaaaaaaaaaab"：
这种要全部循环完，才结束循环
16楼循环2次后，就结束循环


从学习角度说，17#是我想学习的。