全文目录

• ☘前言☘
• 🎁主要知识点
• • 计数排序
• 📓课后习题
• • 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;}

📑写在最后

最近忙于更新自己的一些总结文章，这个系列更新的较晚，大家如果喜欢还希望给个点赞收藏啥的 我会继续更新下去的0.0