专门提供做ppt小素材的网站,网站定位,wordpress设置目录,长沙网站建设的公司今天是基础数据结构的最后一个。至此我们的基础数据结构系列就结束了!!! 这几天先告一段落#xff0c;等期末考试完继续更新算法系列。 哈希表又叫散列表#xff0c;通常用数组来实现#xff0c;又叫做哈希数组。
一、概念
常用哈希函数
1、直接定址法#xff1b; 关键字…今天是基础数据结构的最后一个。至此我们的基础数据结构系列就结束了!!! 这几天先告一段落等期末考试完继续更新算法系列。 哈希表又叫散列表通常用数组来实现又叫做哈希数组。
一、概念
常用哈希函数
1、直接定址法 关键字本身就是哈希值例如f(x) x; 2、平方取中法 3、折叠法 4、除留取余法常用 f(x) x % m 5、位与法
哈希冲突解决方法
1、开放定址法 如果发生冲突则寻找下一个空地址。 2、链地址法 发生冲突后不换地址使用链表将链接到当前的值的后面
第一题 41. 缺失的第一个正数
int hash[500002]; //定义哈希数组int firstMissingPositive(int* nums, int numsSize) {memset(hash, 0, sizeof(hash)); //初始化为0// 遍历数组,传入哈希for(int i 0; i numsSize; i) {int v nums[i];//如果值负数或大于500000,那后面就不用看了,因为数组长度只有500000,里面必定有空值。if(nums[i] 0 || nums[i] 500000) {continue;}hash[ v ] 1;}for(int i 1; ; i) {if(!hash[i]) {return i;}}return -1;
}第二题 387. 字符串中的第一个唯一字符
int firstUniqChar(char* s) {int hash[26];memset(hash, 0, sizeof(hash));//遍历数组的方法如果出现一次字符则1for(int i 0; s[i]; i) {hash[s[i] - a];}// 遍历数组判断当前对应的哈希表是否为1返回索引值即可for(int i 0; s[i]; i) {if(hash[s[i] - a] 1) {return i;}}return -1;
}第三题 215. 数组中的第K个最大元素
#define BASE 10000
int hash[2 * BASE 5];int findKthLargest(int* nums, int numsSize, int k) {memset(hash, 0, sizeof(hash));for(int i 0; i numsSize; i) {int index nums[i] BASE;hash[index];}for(int i 2 * BASE; i 0; --i) {while( hash[i] ) {k--;hash[i]--;if( k 0 ) {return i - BASE;}}}return -1;
}第四题 1. 两数之和
hash[i]代表数字i hash[i] target;
/*** Note: The returned array must be malloced, assume caller calls free().*/
//实现哈希表
#define BIT 16 //定义16位,我也不知道什么意思
#define MASK ((1 BIT) - 1) //说是掩码,就是2^16 - 1 65535
#define MAGIC 1000000001 //定义一个边界,用于初始化哈希表
int hash[MASK 1]; //创建哈希表//初始化哈希表
void HashInit() {//里面的值都赋值为取不到的值,表示为空for(int i 0; i MASK; i) {hash[i] MAGIC;}
}int HashFindAndInsert( int x ) {int v x MASK; //于操作,等于将x变为正数,如果不是负数则就是xwhile(1) {//如果当前哈希数组为空则插入if(hash[v] MAGIC) {hash[v] x;return v;}else if(hash[v] x) { //如果是x表明已经插入了,直接返回return v;}v (v 1) * MASK; //如果不满足要求,v往前移动一位,直到满足要求}
}int pos[MASK 1];
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int *ret (int *)malloc(sizeof(int) * 2);*returnSize 2;HashInit();memset(pos, -1, sizeof(pos));for(int i 0; i numsSize; i) {int idx HashFindAndInsert(target - nums[i]); //得到target - b a里面的aif(pos[idx] ! -1) {ret[0] pos[idx];ret[1] i;return ret;}//pos[ HashFindAndInsert(nums[i]) ] i;}*returnSize 0;return ret;
}
