文章目录
零、写在前面
一、主要知识点
归并排序
二、课后习题
164. 最大间距
912. 排序数组
217. 存在重复元素
169. 多数元素
面试题 10.01. 合并排序的数组
148. 排序链表
写在最后
零、写在前面
今天是打卡的第36天，今天的难度一般般，赶紧写写复习考试了-.-知识点在：
《算法零基础100讲》(第36讲) 排序进阶 - 归并排序
一、主要知识点
c语言中常见的排序方式
归并排序
划分中间位置为分割点，对分割后的元素进行排序，其中利用了选择排序的相对有序情况下时间复杂度较低的特性。
int a[maxn]; void MergeSort(int *nums, int l, int r) { int i, mid, p, lp, rp; int *tmp = (int *)malloc( (r-l+1) * sizeof(int) ); //辅助数组 if(l >= r) { return ; //只有一个元素 } mid = (l + r) >> 1; // 划分 MergeSort(nums, l, mid); // 排序右边 MergeSort(nums, mid+1, r); // 排序左边 p = 0; // 辅助数组指针 lp = l, rp = mid+1; // 指向左右两边的元素 while(lp <= mid || rp <= r) { // 双指针判断 if(lp > mid) { tmp[p++] = nums[rp++]; // 左部分插入完了 }else if(rp > r) { tmp[p++] = nums[lp++]; // 右部分插入结束 }else { if(nums[lp] <= nums[rp]) { // 选择较小的插入 tmp[p++] = nums[lp++]; }else { tmp[p++] = nums[rp++]; } } } for(i = 0; i < r-l+1; ++i) { nums[l+i] = tmp[i]; // 写回 } free(tmp); // 释放空间 }
二、课后习题
164. 最大间距
164. 最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
解题思路
先排序然后用max记录最大值 返回就好了？
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++) if(max < nums[i] - nums[i - 1]) max = nums[i] - nums[i - 1];//更新值 return max; }
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; }
217. 存在重复元素
217. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。。
解题思路
直接排序就好了，如果两个元素相同就返回false
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; }
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; }
面试题 10.01. 合并排序的数组
面试题 10.01. 合并排序的数组
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
解题思路
这个如果采用辅助元素啥的，都是浪费空间，最简单的就是从后往前进行二路归并排序。这样不会产生覆盖问题。
void merge(int* A, int ASize, int m, int* B, int BSize, int n){ int k = m + n -1, low = m - 1,high = n - 1; //k为最终数组指针 while(low != -1|| high != -1){//A或B还有元素 if(low != -1 && high != -1) //A和B都有元素 if(A[low] < B[high]) A[k--] = B[high--]; else A[k--] = A[low --]; else if(low != -1) A[k--] = A[low--]; //将所有B插入 else A[k--] = B[high--]; //将所有A插入 } }
148. 排序链表
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
解题思路
我用一个数组把所有的节点存进去，然后排序，然后再链接起来0.0
bool sort(const struct ListNode **a,const struct ListNode **b){ struct ListNode *p = *a, *q = *b; return p->val > q->val; } struct ListNode* sortList(struct ListNode* head){ if(!head) return head; struct ListNode *a[50001]; int len = 0; while(head){ //插入表中 a[len++] = head; head = head->next; } qsort(a,len,sizeof(struct ListNode* ),sort);//对表内元素按照val大小排序 for(int i = 0;i<len - 1;++i){ //链接起来 a[i]->next =a[i+1]; //printf("%d",a[i]->val); } a[len -1]->next = 0; //最后的NULL return a[0]; //返回第一个元素 }
