目录
零、写在前面
一、主要知识点
1.冒泡排序
二、课后习题
75. 颜色分类
4. 寻找两个正序数组的中位数
747. 至少是其他数字两倍的最大数
写在最后
零、写在前面
今天是打卡的第33天，今天的难度巨低，难道因为大家都要考试了？知识点在：
《算法零基础100讲》(第33讲) 排序入门 - 冒泡排序https://blog.csdn.net/WhereIsHeroFrom/article/details/121463964
https://blog.csdn.net/WhereIsHeroFrom/article/details/121463964
一、主要知识点
1.冒泡排序
每次将最大的元素冒到最后，那么最后几个元素就是局部有序的。
需要注意的是交换的时候进行标记，如果一趟冒泡里没有发生任何一次交换，说明已经有序，可以提前退出。
#define Type int void Swap(Type* a, Type* b) { Type tmp = *a; *a = *b; *b = tmp; } void BubbleSort(int n, Type *a) { bool swapped; int last = n; do { swapped = false; for(int i = 0; i < last - 1; ++i) { if(a[i] > a[i+1]) { //冒泡 Swap(&a[i], &a[i+1]); swapped = true; // 标记交换 } } --last; }while (swapped);//无论怎样 最后只剩一个元素的时候一定不会发生交换 } void sortColors(int* nums, int numsSize){ BubbleSort(numsSize, nums); }
二、课后习题
75. 颜色分类
75. 颜色分类
https://leetcode-cn.com/problems/sort-colors/
题目描述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
思路
花里胡哨，乱七八糟，就是让你排序罢了。。从小到大那种0.0
void swap(int *a,int *b){ *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } void sortColors(int* nums, int numsSize){ for(int i = 0;i < numsSize - 1;i++){ bool temp = false; //判断是否有交换 for(int j = 1;j < numsSize - i;j++) if(nums[j] < nums[j - 1]) swap(&nums[j],&nums[j - 1]),temp = true; if(!temp) break; } }
4. 寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
思路
这个有点二路归并排序的感觉了，但是我们要做的只是找到中间的两个元素罢了。我就直接记住中间两个元素就完事了。你如果问如果是奇数中间只有一个？我就计两遍！
就可以统一结果啦。是不是很机智？
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){ int mid1,mid2,ans = 0; //记录中间的两个位置在哪里 if((nums1Size+nums2Size)&1) mid1=mid2= (nums1Size +nums2Size)/2; else mid2 = (nums1Size + nums2Size) / 2,mid1 = mid2 - 1; int low = 0,high = 0,count = 0;//双指针归并排序 while(count < nums1Size + nums2Size){ int temp; //归并计算下个元素 if((high != nums2Size)&&(low != nums1Size)){ if(nums1[low] < nums2[high]) temp = nums1[low++]; else temp = nums2[high++]; } else if(high != nums2Size) temp = nums2[high++]; else temp = nums1[low++]; //到中间位置进行记录 if(mid1 == count) ans += temp; if(mid2 == count) {ans += temp;break;} count++; } return ans/2.0; }
747. 至少是其他数字两倍的最大数
747. 至少是其他数字两倍的最大数
https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others/
题目描述
给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。
思路
找到最大值，然后做判断就好了，没啥难度。
int dominantIndex(int* nums, int numsSize){ if(numsSize == 1) return 0; int max = -1,mini; for(int i = 0;i < numsSize;i++) if(max < nums[i]) max = nums[i],mini = i;//找到最大值 for(int i = 0;i < numsSize;i++) if(i != mini && max < 2*nums[i]) return -1; return mini; }
