C++ 算法：统计数列中每个数前面比它大的数字数量

楠楠最近在研究南海区 5 年级英语成绩的排序有关算法，如果数列中的数是从小到大排列的，则称有序的。

研究中对于没有排好序的数列，要统计每个数前面有多少比它大的数字。比如有 5 个数的数列： 31425，则第 1 个数 3 之前有 0 个数比它大；第 2 个数 1 之前有 1 个数比它大；第 3 个数 4 之前有 0 个数比它大；第 4 个数 2 之前有 2 个数比它大；第 5 个数 5 之前有 0 个数比它大。由于数列很长，楠楠求你编程来统计。

输入格式

第一行 1 个整数 N，表示数列有 N 个整数。

第二行有 N 个非负整数，每个数表示一个分数，范围是 [0…120]。

输出格式

一行 N 个非负整数(中间有空格)，第 i 个数表示原数列中第 i 位前有多少比第 i 位数大。

输入输出样例

样例 1 输入样例

5
3 1 4 2 5

输出样例

0 1 0 2 0

数据范围与提示

8 个数据： N 的范围是 [1…1000]，每个数范围是 [0…120]

2 个数据： N 的范围是 [1…1,00,000]，每个数范围是 [0…120]

内容：

题目要求统计一个数列中每个数前面有多少比它大的数字。首先，我们可以使用一个循环遍历数列中的每个数。对于每个数，再使用一个循环比较它之前的数，如果有比它大的数，则统计数量加1。最后输出统计结果。

具体的代码如下：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    vector<int> count(n, 0);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[i]) {
                count[i]++;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << count[i] << " ";
    }

    return 0;
}

时间复杂度分析：外层循环遍历数列中的每个数，内层循环比较该数之前的数。对于每个数，最坏情况下需要比较它之前的所有数，所以内层循环的时间复杂度为O(i)，其中i为数列中的位置。因此，总的时间复杂度为O(n^2)，其中n为数列的长度。