这是平生第一次见交互题(即不需要自己写输入输出)
(算法提高课的y总讲的更好)
zhi识点
1.反对称性:a>b, 就一定b< a;但是关系唯一确定
2.传递性:a>b,b>c $\color{blue}{->}$ a >c
3.n个节点,n*(n-1)/2条边有向边构成的任意有向图:每个点与其他所有点相连,且只有一条有向边,握手原理
4.y总在算法基础课讲二分时,有一句话一直没懂,这题终于体现了:$\color{red}{二分不一定要有单调性(也称\large全序关系)}$
代码1:
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
vector<int> specialSort(int n) {
vector<int> res(1, 1);
for(int i = 2; i <= n; ++ i)
{
int l = 0, r = res.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(compare(res[mid], i)) l = mid;
else r = mid - 1;
}
res.push_back(i);
for(int j = res.size() - 2; j > r; -- j)
{
swap(res[j], res[j + 1]);
}
if(compare(i, res[r])) swap(res[r], res[r + 1]);
}
return res;
}
};
代码2:stale_sort()
stable_sort() 函数完全可以看作是 sort() 函数在功能方面的升级版(复杂度是归并排序,而sort是快速排序)。换句话说,stable_sort() 和 sort() 具有相同的使用场景,就连语法格式也是相同的(后续会讲),只不过前者在功能上除了可以实现排序,还可以保证不改变相等元素的相对位置。
vector<int> specialSort(int N)
{
vector<int> a;
for(int i=1;i<=N;i++) a.push_back(i);
stable_sort(a.begin(),a.end(),compare);
return a;
}
今天是认识她的180天qwq
你这是让我也算吗。。。很大的数字额
算
要是算别人的我肯定算不出来:
而今天2023,.8.6
好样的
哈哈哈快两周年了