全文目录
?前言?
?主要知识点
1.排序 API
2.比较函数
?课后习题
912. 排序数组
169. 多数元素
217. 存在重复元素
164. 最大间距
905. 按奇偶排序数组
137. 只出现一次的数字 II
剑指 Offer II 075. 数组相对排序
539. 最小时间差
976. 三角形的最大周长
881. 救生艇
面试题 10.02. 变位词组
?写在最后
?前言?
今天是算法零基础打卡的第41天，题目本身不难，主要是为了理解基数排序的。上链接：
《算法零基础100讲》(第41讲) C语言 排序 API
全文大约阅读时间： 20min
??作者简介：一个从工业设计改行学嵌入式的年轻人
?联系方式：2201891280(QQ)
?主要知识点
1.排序 API
排序API的作用就是传入一个数组，按照规定规则进行就地排序。
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
参数 说明
base 指向要排序的数组的第一个元素的指针
nitems 由base指向的数组中元素的个数
size 数组中每个元素的大小，以字节位单位。
compar 用来比较两个元素的函数，即函数指针(比较算法的回调函数)
2.比较函数
这里我给一个极度简洁的递增写法。
int cmp1(char *a,char *b){ return *a > *b ? 1 : -1; }
可以知道当 a>b时 返回值就是1，否则就是返回-1.
?课后习题
912. 排序数组
912. 排序数组
给你一个整数数组 nums，请你将该数组升序排列。
解题思路
直接排序返回就好了呗？
int cmp(const void *a,const void *b){ return *(int *)a - *(int *)b; } int* sortArray(int* nums, int numsSize, int* returnSize){ qsort(nums,numsSize,sizeof(int),cmp); *returnSize = numsSize; return nums; }
169. 多数元素
169. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ? n/2 ? 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解题思路
写了好几遍了。。。。因为是大于，所以用一个最多元素和其它元素相消除最终剩下的一定是最多的元素。由这个思想可以写出来下面的代码。
int majorityElement(int* nums, int numsSize){ int maxnum = 0,maxtime = 0; for(int i = 0;i < numsSize;i++){ if(maxtime == 0){ //未选定最大元素 maxnum = nums[i]; maxtime++; } else if(nums[i] == maxnum) maxtime++; else maxtime--; } return maxnum; }
217. 存在重复元素
217. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
解题思路
直接排序，然后顺序查看就好了。如果有重复的就返回true
int cmp(int *a,int *b){ return *a > *b; } bool containsDuplicate(int* nums, int numsSize){ qsort(nums,numsSize,sizeof(int),cmp); for(int i = 1;i < numsSize;i++) if(nums[i] == nums[i-1]) return true; return false; }
164. 最大间距
164. 最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
解题思路
直接排序，然后顺序算间距就完事了。
int cmp(int *a, int *b){return *b < *a;} int maximumGap(int* nums, int numsSize){ qsort(nums ,numsSize ,sizeof(int) ,cmp); int max = 0; for(int i = 1;i < numsSize;i++) //printf("%d",nums[i] - nums[i - 1]); if(max < nums[i] - nums[i - 1]) max = nums[i] - nums[i - 1]; return max; }
905. 按奇偶排序数组
905. 按奇偶排序数组
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
解题思路
按照要求写规则，排就好了。
int cmp(int *a, int *b){ if((*a)&1) //a是奇数 if((*b)&1) return *a > *b;//b也是奇数 else return 1; //偶数在前 else if((*b)&1) return -1; else return *a > *b; } int* sortArrayByParity(int* nums, int numsSize, int* returnSize){ *returnSize = numsSize; qsort(nums,numsSize,sizeof(int),cmp); return nums; }
137. 只出现一次的数字 II
137. 只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
解题思路
用位运算更好玩0.0 因为每个数字都出现了三次，那么每位的数字和一定是3的倍数，余数就是只有一个数字的对应位。
int singleNumber(int* nums, int numsSize){ unsigned ans = 0; for(unsigned i = 0;i < 32;i++){ unsigned temp = 0; for(int j = 0;j < numsSize;j++) temp += (((unsigned) 1<<i)&nums[j])>>i; //计算此位所有元素的和 temp %= 3; //求唯一元素这一位是啥 ans += temp << i; } return ans; //强制类型转换 }
剑指 Offer II 075. 数组相对排序
剑指 Offer II 075. 数组相对排序
给定两个数组，arr1 和 arr2，
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
解题思路
按照要求排就好了。我用了hash表直接映射位置，省的找了。
int hash[1001]; int cmp(int *a,int *b){ if(hash[*a] && hash[*b]) return hash[*a] > hash[*b];//都在2中出现 else if(hash[*a] || hash[*b]) return hash[*a] < hash[*b];//只有一个出现 return *a > *b; //都没出现 } int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize){ memset(hash,0,sizeof(hash)); for(int i = 0;i <arr2Size;i++) hash[arr2[i]] = i + 1;//初始化hash表为位置+1，为了和没有做区分 *returnSize = arr1Size; qsort(arr1,arr1Size,sizeof(int),cmp); return arr1; }
539. 最小时间差
539. 最小时间差
给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
解题思路
直接转化为分钟表示，排序，然后计算最小的时候，初始化为最小和最大的间距就好了。
int cmp(int *a,int*b){ return *a > *b; } int findMinDifference(char ** timePoints, int timePointsSize){ int hash[timePointsSize],hashSize = 0; for(int i = 0;i<timePointsSize;i++) // hash[hashSize++] = (((timePoints[i][0] -'0') * 10) + timePoints[i][1] - '0') * 60 + (timePoints[i][3] - '0')*10 + timePoints[i][4]; //转化为分钟 qsort(hash,hashSize,sizeof(int),cmp); int min = 24*60+hash[0] - hash[hashSize - 1]; for(int i = 1;i < hashSize;i++) if(min>hash[i]-hash[i-1]) min = hash[i] - hash[i-1]; return min; }
976. 三角形的最大周长
976. 三角形的最大周长
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回 0。
解题思路
直接排序，如果最大值减中间值>最小值就可以构成三角形。
int cmp(int *a,int *b){return *a > *b;} int largestPerimeter(int* nums, int numsSize){ qsort(nums,numsSize,sizeof(int),cmp); int i; for(i = numsSize - 1;i > 1;i--){ if(nums[i] < nums[i-1] + nums[i - 2]) break; } if(i == 1) return 0; else return nums[i] + nums[i - 1] + nums[i-2]; }
881. 救生艇
881. 救生艇
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
解题思路
贪心思想，最大值如果不能和最小值同船就只能自己一条船。
int cmp(int *a,int *b){return *a > *b;} int numRescueBoats(int* people, int peopleSize, int limit){ qsort(people,peopleSize,sizeof(int),cmp); int low = 0, high = peopleSize - 1,ans = 0; while(low <= high){ if(people[low] + people[high] > limit) --high; else ++low,--high; ans++; } return ans; }
面试题 10.02. 变位词组
面试题 10.02. 变位词组
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
解题思路
创建一个数据结构，将原始串和排序完的串做映射，因为变位词排序完之后肯定是都相同的。所以可以用strcmp来做判断再做一次排序，然后分表就好了。
typedef struct vs{ char *str; char *vstemp; }vs; int cmp1(char *a,char *b){ return *a > *b; } int cmp2(vs *a,vs *b){ return strcmp(a->vstemp,b->vstemp); } char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes){ vs temp[strsSize]; for(int i = 0;i < strsSize;i++){ temp[i].str = strs[i]; int len = strlen(temp[i].str); temp[i].vstemp = malloc(sizeof(char)*(len+1)); temp[i].vstemp[0] = 0; strcat(temp[i].vstemp,temp[i].str); qsort(temp[i].vstemp,len,sizeof(char),cmp1); //比较字符串的排序 } qsort(temp,strsSize,sizeof(vs),cmp2); //整体排序 int colsize[9900],col,size = 1; colsize[0] = 1; for(int i = 1;i <strsSize;i++){ if(strcmp(temp[i].vstemp,temp[i-1].vstemp)) size++,colsize[size - 1] = 1; else colsize[size-1] ++; } *returnSize = size; (*returnColumnSizes) = malloc(sizeof(int)*size); char ***ans = malloc(sizeof(char **) * size); for(int i = 0;i <size;i++) (*returnColumnSizes)[i] = colsize[i],ans[i] = malloc(sizeof(char *) * colsize[i]); size = 0,col = 0; //写入数据 for(int i = 0;i < strsSize;i++){ if(!colsize[size]) size++,col = 0; int len = strlen(temp[i].str); ans[size][col] = malloc(sizeof(char)*(len +1)); ans[size][col][0] = '\0'; strcat(ans[size][col],temp[i].str); colsize[size]--; col++; } return ans; }
