北大OJ_1007题：DNA Sorting

该题的意思是输入指定数量的字符串，每个字符串的长度一样，找出每个字符串中逆序对，然后按逆序对的升序输出所以的字符串，逆序对相同的则按输入时的顺序输出。

此题的突破点在找逆序对，以下列举两种找出逆序对的方法。

穷举法找逆序对（时间复杂度为O(n^2)）

#include <iostream>
#include <string>
#include <deque>
#include <cmath>
using namespace std;
struct tagString
{
int nInvertedCount;
string strSequence;
};
int main()
{
deque<tagString> mStrList;
tagString mTagString;
short n,m;
cin >> n >> m;
while( m > 0 )
{
cin >> mTagString.strSequence;
int nInvertedCount = 0;
for( string::size_type i = 0; i < mTagString.strSequence.size() - 1; ++i )
{
for( string::size_type j = i + 1; j < mTagString.strSequence.size(); ++j )
{
if ( mTagString.strSequence[i] > mTagString.strSequence[j] )
{
nInvertedCount++;
}
}
}
mTagString.nInvertedCount = nInvertedCount;
if ( mStrList.empty() )
{
mStrList.push_back( mTagString );
}
else
{
int i = mStrList.size()-1;
for ( ; i >= 0; --i )
{
if ( mStrList[i].nInvertedCount > nInvertedCount )
{
continue;
}
break;
}
mStrList.insert( mStrList.begin() + (i + 1), mTagString );
}
--m;
}
for ( deque<tagString>::size_type i = 0; i < mStrList.size(); ++i )
{
cout << mStrList[i].strSequence << endl;
}
return 0;
}

归并排序找逆序对（时间复杂度为O(nlogn)）

#include <iostream>
#include <string>
#include <deque>
#include <cmath>
using namespace std;
int Merge( string& strSrc, int low, int mid, int high )
{
int i = low;
int j = mid + 1;
int nCount = 0;
string strTemp( high - low + 1, 0 );
int k = 0;
while( i <= mid && j <= high )
{
if ( strSrc[i] <= strSrc[j] )
{
strTemp[k++] = strSrc[i++];
}
else
{
strTemp[k++] = strSrc[j++];
nCount += j - k - low;
}
}
while( i <= mid )
{
strTemp[k++] = strSrc[i++];
}
while( j <= high )
{
strTemp[k++] = strSrc[j++];
}
for ( k = 0; k < (high-low+1); ++k )
{
strSrc[low+k] = strTemp[k];
}
return nCount;
}
int MergeSort( string& strSrc, int low, int high )
{
int nCount = 0;
if ( low < high )
{
int mid = ( low + high ) / 2;
nCount += MergeSort( strSrc, low, mid );
nCount += MergeSort( strSrc, mid + 1, high );
nCount += Merge( strSrc, low, mid, high );
}
return nCount;
}
struct tagString
{
int nInvertedCount;
string strSequence;
};
int main()
{
deque<tagString> mStrList;
tagString mTagString;
short n,m;
cin >> n >> m;
while( m > 0 )
{
cin >> mTagString.strSequence;
string strTemp = mTagString.strSequence;
mTagString.nInvertedCount = MergeSort( strTemp, 0, strTemp.size()-1 );
if ( mStrList.empty() )
{
mStrList.push_back( mTagString );
}
else
{
int i = mStrList.size()-1;
for ( ; i >= 0; --i )
{
if ( mStrList[i].nInvertedCount > mTagString.nInvertedCount )
{
continue;
}
break;
}
mStrList.insert( mStrList.begin() + (i + 1), mTagString );
}
--m;
}
for ( deque<tagString>::size_type i = 0; i < mStrList.size(); ++i )
{
cout << mStrList[i].strSequence << endl;
}
return 0;
}

总结

理论上来说，第二种方法要快一些，但是第二种方法里在排序的时候存在很多的交换，在OJ上编译运行反而是第一种方法更快。

作者：山丘儿
转载请标明出处，谢谢。原文地址：http://blog.csdn.net/s634772208/article/details/46568015

最后

以上就是笨笨短靴为你收集整理的北大OJ_1007题：DNA Sorting的全部内容，希望文章能够帮你解决北大OJ_1007题：DNA Sorting所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。