|
最近接触了哈希。
Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
其实简单的解释来说，哈希就是一种映射，一种对应关系。比如这里有一万首歌，给你一首新的歌X，要求你确认这首歌是否在那一万首歌之内。无疑，将一万首歌一个一个比对非常慢。但如果存在一种方式，能将一万首歌的每首数据浓缩到一个数字（称为哈希码）中，于是得到一万个数字，那么用同样的算法计算新的歌X的编码，看看歌X的编码是否在之前那一万个数字中，就能知道歌X是否在那一万首歌中。当然映射也是会存在重复的也就是说，很有可能两首歌对应到了同一个位置，这就叫做哈希冲突，但是一个好的哈希函数是可以避免很多冲突，但是并不能完全解决冲突。
今天首先我要解决的是一个很简单的小问题，就是查找字符串中第一个出现一次的字母。或者说第一个出现N次的字母。虽然这并不难，但是我们要求时间复杂度为O（1），并且空间复杂度也不能很大，如果在以前的话，我们会选择像冒泡排序一样的方法和后边进行一一对比，但是有了哈希的思想处理起来就会更加的简单一些。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i = 0;
char *a = "abcdabcde";
int Hash[26] = { 0 };
while (a[i])
{
Hash[a[i] - 'a']++;
i++;
}
for (i = 0; i < 26; i++)
{
if (Hash[i] == 1)
{
printf("%c", i + 'a');
system("pause");
return 0;
}
}
printf("没有出现一次的字符\n");
system("pause");
return 0;
}
这里就是创建一个26个字母的数组，这里的字符串只能有这26个字母，数组的每个位置也都对应着一个字母，所以当你出现一个字母的时候，对应位置的数组就加1，当最终字符串遍历完成之后，直接判断，那个对应的数组，第一个等于1的位置就是第一个出现一次的字母。
但是，这样是正确的吗？
char *a = "abcdabcde";
char *a = "acdacdeb";
大家看这两个字符串，第一个算出来确实是e，那第二个字符串第一次出现的字符是啥呢？应该是e但是运行出来却是b。为什么，因为你在遍历这个字符串的时候永远是从a开始到z遍历。所以这时候遍历的时候就不能刚从i=0开始遍历了。
i = 0;
while (a[i])
{
if (Hash[a[i] - 'a'] == 1)
{
printf("%c", a[i]);
system("pause");
return 0;
}
i++;
}
这里遍历的时候也要通过你字符串的出现的顺序来遍历的这时候就可以正确找到你的第一个出现的字符了。
这时候如果想判断第K个也是很容易实现的。 | 
转播
