刷题1：成绩排序

troysps

2020-02-21

关注关注

刷题1：成绩排序

来源:https://www.nowcoder.com/practice/0383714a1bb749499050d2e0610418b1
题目：
查找和排序

题目：输入任意（用户，成绩）序列，可以获得成绩从高到低或从低到高的排列,相同成绩
都按先录入排列在前的规则处理。

示例：
jack 70
peter 96
Tom 70
smith 67

从高到低成绩
peter 96
jack 70
Tom 70
smith 67

从低到高

smith 67

jack 70
Tom 70
peter 96

输入描述:
输入多行，先输入要排序的人的个数，然后输入排序方法0（降序）或者1（升序）再分别输入他们的名字和成绩，以一个空格隔开

输出描述:
按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开
示例1
输入

3
0
fang 90
yang 50
ning 70

输出
fang 90
ning 70
yang 50

这是我最近刷的第一道题，虽然是比较简单的题，但是收获不少。先放上我的解法吧，当然不是我写的，是我看讨论里一个高票回答的:

#include<bits/stdc++.h>
using namespace std;
int n,method,score[500],myIndex[500];
string name[500];
bool cmpSmall(int i,int j){
    return score[i]<score[j];
}
bool cmpBig(int i,int j){
    return score[i]>score[j];
}
int main(){
    while(cin>>n){
        cin>>method;
        for(int i=0;i<n;i++){
            cin>>name[i]>>score[i];
            myIndex[i]=i;
        }
        if(method==0){
            stable_sort(myIndex,myIndex+n,cmpBig);
        }
        else{
            stable_sort(myIndex,myIndex+n,cmpSmall);
        }
        for(int i=0;i<n;i++){
            cout<<name[myIndex[i]]<<" "<<score[myIndex[i]]<<endl;
        }
    }
    return 0;
}

收获如下：

本题限制了C/C++ 1秒，而对于该时限，通常，我们所设计的算法复杂度不能超过百万级别，即不能超过一千万。即如果算法的时间复杂度是O(n^2),则n不能大于3000.这对于我们选择算法是有意义的。而且据我所知，一般的题目都是对时间要求严格，对空间的要求就松很多。例如本题空间限制：C/C++ 32M，其实运行下来实际使用的就几百k。所以可以考虑采用一些空间换时间的操作，例如本题中有人想到的利用成绩的离散性和有限性做哈希表，把name往各个位置插，这个思路不错，我写了一下:

#include<bits/stdc++.h>
using namespace std;
int n,method;
vector<vector<string>*> myHash;
int main(){
    for(int i=0;i<101;i++){
        myHash.push_back(new vector<string>());
    }
    int score;
    string name;
    while(cin>>n){
        cin>>method;
        for(int i=0;i<n;i++){
            cin>>name>>score;
            myHash[score]->push_back(name);
            name.clear();
        }
        if(method==0){
            for(int i=100;i>=0;i--){
                if(!myHash[i]->empty()){
                    int length=myHash[i]->size();
                   for(int j=0;j<length;j++){
                       cout<<myHash[i]->at(j)<<" "<<i<<endl;
                   }
                }
            }
        }else{
             for(int i=0;i<=100;i++){
                if(!myHash[i]->empty()){
                    int length=myHash[i]->size();
                   for(int j=0;j<length;j++){
                       cout<<myHash[i]->at(j)<<" "<<i<<endl;
                   }
                }
            }
        }
    for(int i=0;i<101;i++){
        myHash[i]->clear();
    }
    }
    return 0;
}

但是它的实际表现不如第一个解法，无论是时间上还是空间上。虽然第一个解法因为有排序，是O(lgn)的，但是使用的都是基本数据类型，也不涉及到对象的动态申请和释放；第二种虽然是O(n)的，但是使用了STL，每次用完还要释放内容，所以相比还是慢一些，当然空间占用更大是必然的了。从编写上来看，也是第一种比较简单，不容易出错，毕竟stable_sort是写好的库函数。

c++ 有一个和Java容易混的地方，就是它的string\list等等首字母都是小写的，这个平常用不是什么问题，但是像OJ这种提示不完全的有时候还是挺坑的
还有一个坑的地方在于，因为用了万能头文件<bits/stdc++.h>,把c++ 的标准库都一股脑导入进来了，就特别容易发生关键字的重复。我个人觉得比较方便的解决办法就是在变量前面加个my,特别是一些看着就比较“标准”的变量名，例如map\index\hash等等
c++ 的vector才是可以使用at(int index)或者下表随机访问的,list是链表，不能随机访问，这个和java还是有区别的
为啥说了这么多c++ 和java的区别，我本人也是对java更熟悉，却还是要用C++，因为我发现像算法OJ还是C++ 适合，一个是写起来简单（Java的import还有语句都是比较复杂的，只是在IDE下写的爽而已），另一个就是速度比较快，并且c++ 格式简单，写一个main就开干，java还要慢悠悠地创建类
像STL和struct还有class都是创建对象适合不需要使用new语句的，new创建出来的都是指针
区分length()和size()的含义：length()说的是长度，一般用在string上面，说字符串的长度；而size是大小，一般用在vector\list上，指的是个数
说回第一种解法，这里用到了自定义排序规则的写法。像sort函数默认是升序，默认的compare规则也是 return a<b.如果想要降序排列，可以自定义规则为return a>b(规律就是，return的大小规律和升降时候谁在前的规律一样）。但是这里这个算法实现了一个我之前一直觉得比较麻烦的事情，就是对多个项按项中的某一个指标排序。因为它有连带信息，所以不能用一个基本类型存放，而如果只对排序指标所在的基本类型排序的话从属关系会乱掉。我之前的思路是使用结构体然后自定义排序规则，使得比较结构体中的一项。但是这个算法只要基本类型就实现了，思路就是对下标排序，但是比较函数中比较的是指标。这样得到的就是按指标排好序的下标，顺序体现的是指标的大小，而信息的从属关系由下标的值保存着，很巧妙的设计。
注意sort的参数输入的是begin,end,comp.不要把长度输入进去了，end=begin+n