多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:176, 178, 180, 170, 171这些捣乱分子对为 <176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>,<180, 171>, 那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可, 不用具体的对) 要求： 输入: 为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。 输出： 为一个文件(out)，每行为一个数字，表示捣乱分子的对数。 详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的代码 ，并分析时间复杂度。 限制： 输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。
我想说此题就是一个逆序对的问题，一般的解法都是nlogn的时间复杂度
这个算法采用的原型是二分排序算法，解逆序对的算法还有很多。
这道题是
http://www.nowcoder.com/practice/bb06495cc0154e90bbb18911fd581df6?rp=3&ru=/ta/cracking-the-coding-interview&qru=/ta/cracking-the-coding-interview/question-ranking
实在不懂可以直接参看网页中的“算法视频讲解”
classAntiOrder {
public:
intTemp[100000];
intcountX(vector
if(s == e){
Temp[s]= (*A)[s];
return0;
}
else{
intk = (s+e)/2;
intans = countX(A,s,k)+countX(A,k+1,e);
inti = s,j = k+1,l = s;
if(l <= e){
while( i <= k && j <= e){
if((*A)[i] > (*A)[j]){
ans += (k-i+1);
Temp[l++] = (*A)[j++];
}
elseif((*A)[i] < (*A)[j]){
Temp[l++] = (*A)[i++];
}
else{
Temp[l++] = (*A)[i++];
Temp[l++] = (*A)[j++];
}
}
while(i <= k){
Temp[l++] = (*A)[i++];
}
while(j <= e){
Temp[l++] = (*A)[j++];
}
}
while(s<=e){
(*A)[s] = Temp[s];
s++;
}
returnans;
}
}
intcount(vector
// write code here
returncountX(&A,0,n-1);
}
};
