请教一个排序的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一个排序的问题

请教一个排序的问题# JobHunting - 待字闺中

a*r2011-05-23 07:05

1 楼

a是一个一维数组，包含7个元素。想用Algorithm里的sort算法对a进行排序,可是如何能打印a数组内元素的对应序号呢？
vector va;
vector ::iterator aIter;
for (int i=0;i<7; i++)
{
va.push_back(a[i]);
}

sort(va.begin(),va.end());
比如a[3]={4,1,5},排序完之后打印出1,4,5。如何返回1,0,2这个对应序号？
或者使用其他STL函数也可以的。

谢谢各位前辈

d*l2011-05-23 07:05

2 楼

stl本身没有这种东西，你可以自己维护这个信息。有什么要求吗？如果没什么要求，
你直接开一个vector >，push_back(make_pair(a[i],i))再sort不就行了

何能打印a数组内元素的对应序号呢？

【在 a******r 的大作中提到】

: a是一个一维数组，包含7个元素。想用Algorithm里的sort算法对a进行排序,可是如何能打印a数组内元素的对应序号呢？
: vector va;
: vector ::iterator aIter;
: for (int i=0;i<7; i++)
: {
: va.push_back(a[i]);
: }
:
: sort(va.begin(),va.end());
: 比如a[3]={4,1,5},排序完之后打印出1,4,5。如何返回1,0,2这个对应序号？

i*e2011-05-23 07:05

3 楼

vector > va;
for (int i = 0; i < n; i++) {
va.push_back(pair(a[i], i));
}
sort(va.begin(), va.end());
for (int i = 0; i < n; i++) {
cout << va[i].second << " ";
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

y*g2011-05-23 07:05

4 楼

map m;
for(int i=0;i<7;i++) {
m[a[i]]=i;
}
for(map::iterator it = m.begin();it!=m.end();++it) {
it->first; //1, 4,5
it->second; //1,0,2
}

何能打印a数组内元素的对应序号呢？

【在 a******r 的大作中提到】

d*l2011-05-23 07:05

5 楼

需要考虑下数组中有重复元素的情形

【在 y*******g 的大作中提到】

: map m;
: for(int i=0;i<7;i++) {
: m[a[i]]=i;
: }
: for(map::iterator it = m.begin();it!=m.end();++it) {
: it->first; //1, 4,5
: it->second; //1,0,2
: }
:
: 何能打印a数组内元素的对应序号呢？

y*g2011-05-23 07:05

6 楼

有道理

【在 d*******l 的大作中提到】

: 需要考虑下数组中有重复元素的情形

w*s2011-05-23 07:05

7 楼

何能打印a数组内元素的对应序号呢？
自己写一个compare函数就可以了:
bool compare(int a, int b) {
return va[a] < va[b];
}
然后
vector index;
for (int i = 0; i < va.size(); ++i) {
index.push_back(i);
}
sort(index.begin(), index.end(), compare);

【在 a******r 的大作中提到】

a*r2011-05-23 07:05

8 楼

多谢ls几位。3楼的code很好用～l

c*t2011-05-23 07:05

9 楼

pair的大小比较是按照first来比较的？
谢谢！

【在 i**********e 的大作中提到】

: vector > va;
: for (int i = 0; i < n; i++) {
: va.push_back(pair(a[i], i));
: }
: sort(va.begin(), va.end());
: for (int i = 0; i < n; i++) {
: cout << va[i].second << " ";
: }
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2011-05-23 07:05

10 楼

是的。但如果 first 是一样，那就会比较 second.
From http://www.cplusplus.com/reference/std/utility/pair/:
In inequality comparisons (), only the first element is compared, except
if both first elements compare equal to each other, in this case only the
second element is taken into consideration for the comparison operation.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 c*********t 的大作中提到】

: pair的大小比较是按照first来比较的？
: 谢谢！