全文目录
☘前言☘
🎁主要知识点
计数排序
📓课后习题
242. 有效的字母异位词
215. 数组中的第K个最大元素
389. 找不同
645. 错误的集合
268. 丢失的数字
📑写在最后
☘前言☘
今天是算法零基础打卡的第39天，今天我先更新题解再写文章。上链接：
《算法零基础100讲》(第39讲) 非比较排序 - 计数排序
全文大约阅读时间： 20min
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
🎁主要知识点
计数排序
与hash表类似，将所有元素映射到hash表的下标中。
void CountingSort(int n, int *a) { // 记数排序 int i, top; memset(cnt, 0, sizeof(cnt)); // 初始化hash表 for(i = 0; i < n; ++i) { // 插入元素 ++cnt[ a[i] ]; } top = 0; // 输出数组顶部元素 for(i = 0; i < maxk; ++i) { while(cnt[i]) { // 插入所有这个值 a[top++] = i; --cnt[i]; } if(top == n) { // 插入了所有的元素提前跳出 break; } } }
📓课后习题
242. 有效的字母异位词
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
解题思路
先利用s做插入，然后利用t做减去，所有hash表都是0就是true，否则false。
bool isAnagram(char * s, char * t){ int hash[26] = {0}; for(int i = 0;s[i];++i)//插入s hash[s[i] - 'a']++; for(int i = 0;t[i];++i)//减去t if(hash[t[i] - 'a']) hash[t[i]-'a']--; else return false; for(int i = 0;i < 26;++i)//检查 if(hash[i]) return false; return true; }
215. 数组中的第K个最大元素
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
解题思路
反正就20000个元素，直接用hash表做插入，然后从大到小检测，到第k个元素的时候返回就好了。
char hash[20001];//开堆放爆栈-.- int findKthLargest(int* nums, int numsSize, int k){ memset(hash,0,sizeof(hash));//初始化 for(int i = 0;i < numsSize;i++)//插入 hash[nums[i] + 10000] ++; for(int i = 20000;i > -1;i--)//检测 if(hash[i]){ k -= hash[i]; if(k <= 0) return i-10000;//此次符合要求 } return 0; }
389. 找不同
389. 找不同
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
解题思路
位运算yyds，反正就一个不一样，异或一遍剩的就是它。
char findTheDifference(char * s, char * t){ char ans = 0; for(int i = 0;s[i];i++)//异或所有s ans ^= s[i]; for(int j = 0;t[j];++j)//异或所有t ans ^= t[j]; return ans; }
645. 错误的集合
645. 错误的集合
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
解题思路
直接hash表就好了，最多也就10000个元素。然后用bool就好。重复元素在遍历的时候顺带拉出来。然后丢失数字扫描所有hash表。
int* findErrorNums(int* nums, int numsSize, int* returnSize){ bool hash[numsSize+1]; memset(hash,0,sizeof(hash)); int *ans = malloc(sizeof(int) * 2); *returnSize = 2; for(int i = 0;i < numsSize;i++){ if(hash[nums[i]]) ans[0] = nums[i];//重复数字 hash[nums[i]] = 1; } for(int i = 1;i < numsSize + 1;i++)//找丢失 if(!hash[i]) {ans[1] = i;break;} return ans; }
268. 丢失的数字
268. 丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
解题思路
骚一点，把0-n进行一遍异或，然后异或所有的数组剩下的结果就是要的数字0.0
int missingNumber(int* nums, int numsSize){ unsigned ans = 0; for(int i = 0;i < numsSize;++i)//异或所有0-n ans ^= nums[i]; for(int i = 0;i < numsSize + 1;i++)//遍历 ans ^= i; return ans; }
