目录
零、写在前面
一、主要知识点
1.选择排序
二、课后习题
611. 有效三角形的个数
769. 最多能完成排序的块
写在最后
零、写在前面
今天是打卡的第34天，今天的难度还行，赶紧写写复习考试了-.-知识点在：
《算法零基础100讲》(第34讲) 排序入门 - 选择排序
https://blog.csdn.net/WhereIsHeroFrom/article/details/121484862
一、主要知识点
1.选择排序
每次选择一个最小的元素与当前位置元素交换，保证前半部分有序。
void SelectionSort(int n, Type *a) { int i, j; for(i = 0; i < n - 1; ++i) { int min = i; //记录最小值位置 for(j = i+1; j < n; ++j) { if(a[j] < a[min]) { min = j; } } Swap(&a[i], &a[min]); } }
二、课后习题
611. 有效三角形的个数
611. 有效三角形的个数
https://leetcode-cn.com/problems/valid-triangle-number/
题目描述
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
思路
先进行排序，针对每一个值只需要保证最小值加次小值 > 最大值 就可以形成一个三角形了。
其中根据次小值找最大值可以使用最大值的指针，可以避免回溯。
void swap(int *a,int *b){ *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } void selectsort(int *nums,int numsSize){//插入排序 就是用用-.- for(int i = 0;i < numsSize - 1;i++){ int min = nums[i],mini = i; for(int j = i + 1;j < numsSize;j++) if(nums[j] < min) min = nums[j],mini = j; if(mini != i) swap(&nums[i],&nums[mini]); } } int triangleNumber(int* nums, int numsSize){ int ans = 0; selectsort(nums,numsSize); for(int i = 0;i < numsSize - 2;i++){//最小值 int k = i; //最大值 for (int j = i + 1; j < numsSize; ++j) {//次小值 while (k + 1 < numsSize && nums[k + 1] < nums[i] + nums[j]) { ++k; } ans += fmax(k - j, 0); //防止K < j 情况 } } return ans; }
769. 最多能完成排序的块
769. 最多能完成排序的块
https://leetcode-cn.com/problems/max-chunks-to-make-sorted/
题目描述
数组arr是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
思路
由于包含的元素是确定的就是0-arr.length -1。
本来需要保证的是后面元素的最小值 大于前面元素的最大值。但是这道题的特殊性。
所以如果前k个元素的最大值为 k-1 表示这个可以进行一个排序分块。
基于这样的思路，代码很容易写出来。
int maxChunksToSorted(int* arr, int arrSize){ int max = -1,ans = 0; for(int i = 0;i < arrSize;i++){ if(arr[i] > max) max = arr[i]; if(max == i) ans++; //可进行分快点 } return ans; }
