[数据结构与算法]PAT (Basic Level) 1047 统计同成绩同学

1047 统计同成绩同学

PTA 1047 统计同成绩同学

• 我做此题的想法
  • 我第一想到（最简单）
    两层循环，k*n的复杂度，但超时
  • 第二想到
    先排序，后二分查找，再两个while往左右扩判断是否相同,正确
  • 第三想到multiset容器
    简单粗暴，还是超时,理解好set
• 总结
  • 第一应想查找
    • 顺序表查找
    • 有序表查找
    • 散列表查找（最好）
  • 最佳做法
    • 直接创建一个sorce[101]记录，下标即成绩，sorce[分数]++即可
    • 理论：哈希数组直接映射，因为成绩有限，特别经典

代码

• 最佳做法比较简单，就不写了。

//第二想到正确，不会超时
//先排序，后二分查找，再两个while往左右扩判断是否相同
#include<iostream>
using namespace std;
#include<algorithm>
int find(int target, int* arr, int arrIndex, int len) {
    int sum = 0;
    int tmp = arrIndex;
    //左找右找，巧妙运用短路逻辑防止越界
    while (arrIndex > 0 && arr[--arrIndex] == target) {
        sum++;
    }         
    while (tmp < len - 1 && arr[++tmp] == target) {
        sum++;
    }
    return sum;
}
int main() {
    int numStu;
    cin >> numStu;
    int* arrSorce = new int[numStu];
    for (int i = 0; i < numStu; i++) {
        cin >> arrSorce[i];
    }
    //排序形成有序表，利用有序表查找中的二分查找
    sort(arrSorce, arrSorce + numStu);
    int numFind;
    cin >> numFind;
    int* arrFind = new int[numFind];
    for (int i = 0; i < numFind; i++) {
        cin >> arrFind[i];
    }
    int* arrResult = new int[numFind];
    //二分查找
    for (int i = 0; i < numFind; i++) {
        arrResult[i] = 0;
        int left = 0, right = numStu - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (arrFind[i] < arrSorce[mid]) {
                right = mid - 1;
            }
            else if (arrFind[i] > arrSorce[mid]) {
                left = mid + 1;
            }
            //相等
            else {
                arrResult[i]++;
                //左右查找
                arrResult[i] += find(arrFind[i], arrSorce, mid, numStu);
                break;
            }
        } 
    }
    for (int i = 0; i < numFind; i++) {
        cout << arrResult[i];
        if (i != numFind - 1) {
            cout << " ";
        }
    }
    delete[] arrSorce;
    delete[] arrFind;
    delete[] arrResult;
    return 0;

}

//第三想到multiset容器,最后一个测试点超时了
set容器的插入都是logn的复杂度，插入时超时了
#include<iostream>
#include<set>
using namespace std;
int main() {
    multiset<int>sorce;
    int numStu;
    cin >> numStu;
    while (numStu--) {
        int tmp;
        cin >> tmp;
        sorce.insert(tmp);
    }
    int numFind;
    cin >> numFind;
    while (numFind--) {
        int tmp;
        cin >> tmp;
        cout << sorce.count(tmp);
        if (numFind != 0)
            cout << " ";
    }
    return 0;
}