学步园

译文:http://blog.sina.com.cn/s/blog_61eccf0e0100epql.html

[英文确实有点烂,看不懂]

思路:

找逆序数[一个字符串开始从头到尾遍历,比较,肯定不是一个很好的算法,再加上外层的string数组循环,时间复杂度应该在n^3.采取每个string,从后向前遍历,相应的字符做下标记.这样可以控制在n^2]

--->排序[string一个数组,存放逆序数一个数组,如果对逆序数进行sort后,怎样将与string对应一起呢? 我能想到的是map,不知道各位还有什么好的方法.c++中有multimap.还有一个复杂的思路:循环遍历逆序数数组,每次找其中的最小的数字,输出string[没有排序的逆序数数组的下角标与string数组的下角标对应],然后将这次最小的数字置为一个MaxValue,重复,时间复杂度在n^2]

-->输出,上面使用的multimap进行匹配.只是输出问题了

代码:

//============================================================================
// Name        : 1007.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

int main() {
	int aT=0;
	int cT=0;
	int gT=0;
	string str;
	string strArry[1000];
	int sortedNess[1000]={0};
	int sortedArry[1000]={0};
	int inputLen=0;
	int num=0;
	multimap<int,string> maps;
	cin>>inputLen>>num;
	int i=0;
	int j=0;
	for(;i!=num;i++)
	{
		//reset temp var
		aT=0;
		cT=0;
		gT=0;
		cin>>str;
		strArry[i]=str;
//		cout<<"Test:"<<str<<endl;
		for(j=inputLen-1;j!=-1;j--)
		{
			switch (str[j])
			{
			case 'A':
				aT++;break;
			case 'C':
				sortedNess[i]+=aT;
				cT++;
				break;
			case 'G':
				sortedNess[i]=sortedNess[i]+(cT+aT);
				gT++;
				break;
			case 'T':
				sortedNess[i]=sortedNess[i]+(cT+aT+gT);
				break;
			}
		}
		maps.insert(make_pair(sortedNess[i],str));
	}
	sort(sortedNess,sortedNess+num);
	//deal with repeating data
	j=i=1;
	int temp=sortedNess[0];
	sortedArry[0]=sortedNess[0];
	for(;i!=num;i++)
	{
		if(temp!=sortedNess[i])
		{
			sortedArry[j++]=sortedNess[i];
			temp=sortedNess[i];
		}
	}
	if(j>0)
	{
		num=j;
	}
/*
	for(int temp=0;temp!=num;temp++)
	{
		cout<<"Test_Array:"<<sortedArry[temp]<<endl;
	}
	*/

	j=0;
	typedef multimap<int,string>::iterator iterator_maps;
	iterator_maps it1;

	for(;j!=num;j++)
	{
		pair<iterator_maps,iterator_maps> pos =maps.equal_range(sortedArry[j]);
		while(pos.first!=pos.second)
		{
			cout<<pos.first->second<<endl;
			++pos.first;
		}
	}
	return 0;
}

问题&心得:

碰到一个问题,自己没有考虑到.当出现相同的逆序数时,数组中有N相同的逆序数排在一起,但是在multimap中只要有相同的数据就可以一次性输出,造成了N*N次输出.第一次提交失败.后来又更改将逆序数相同的数据删除[重新创建一个数组,避免有相同的逆序数.]

主要学习了c++中的multimap的使用.提交后运行0MS,时间复杂付控制在n^2,但是内存占据的多些,和分配的几个数组有关吧.

看到很多大神[c++]只用了很少的内存,很短时间,很少的代码.Accepted....很多题目都是这样..只能膜拜......

附上测试数据:主要就是考虑逆序数相同时,输出正确,而且要排序稳定.对于multimap,个人认为,出现相同的key时,分配在内存中应该是按照输入的顺序进行存放的.以后了解深入进行验证.

10 9
TTTTTTTTTC
TTTTTTTTTA
TTTTTTTTTG
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT