问题描述:
有N个元素,编号为1,2,3… N 。 每一对元素的大小关系是确定的。关系具有反对称性。
将这些元素排成一排,每个元素都小于右边与它相邻的元素。
问题转换:
此题可以描述成以下问题 :
对于N个顶点的图,每个顶点跟其他任意顶点之间都有一条有向边。
求此图的一条路径,使其经过并且只经过一次图中所有顶点。(哈密顿路径)
解法探究:
胡言乱语:刚看到题的时候,我的想法是拓扑排序。可是拓扑排序的时间复杂度是n+e。并且也不符合题中“每个元素都小于右边的邻居”这一要求。而且有环路的图也不存在拓扑排序。
看了一些题解后,我想补充一下y总在讨论区提到的命题的证明:
任意有向完全图(又称竞赛图)都存在Hamilton路径。
数学归纳法:
-
N = 1时, 命题显然成立
-
设N = k时成立: 则图中存在一条链,如下
1->2->3->4 -> .... -> k
-
新加入一个节点k+1
- 若其存在出边,设其存在某条出边(绿色)紧跟在入边后面,那么在原链中添加这两个边。构成一个长度为k+1的哈密顿路径。
- 若不存在出边,可直接将其接到k的后面。
- 若不存在入边,可直接将其接到1的前面
所以命题得证。
通过上述数学归纳,可以得出此问题的一个解法,即类似于插入排序的方法寻找我们需要的插入点。
可是插入排序的比较次数是O(n^2)的,明显大于题目中要求的n*logn的比较次数。这个时候就要想到二分了。
我们知道
1. 如果某个位置是入边,那么在它后面的边仅可能存在两种情况:存在或者不存在出边(废话
这两种情况都是可以 将k+1插入的
2. 如果某个位置是出边, 那么在它前面的边也仅可能存在两种情况,存在或者不存在入边
这两种情况也都是可以 将k+1插入的
3. 这样就可以愉快的二分了。
AC代码如下:
class Solution {
public:
int binSearch(vector<int> &v, int x){
int r = v.size();
int l = 0;
int m = (l + r) >> 1;
while(r-l >= 1){ //整个循环过程中,保证l-1处不是出边
if(compare(v[m], x)){
l = m+1;
}
else{
//printf("--");
r = m;
}
m = (r+l) >> 1;
}
//printf("%d ", l);
return l-1;
}
vector<int> specialSort(int N) {
vector<int> v = {1};
for(int i = 2; i <= N; i++){
int x = binSearch(v, i);
v.insert(v.begin() + x + 1, i);
}
return v;
}
};