我的代码的复杂程度是什么，我该如何改善？

Question

这是CSES问题集中的问题。

有n个申请人和m个免费公寓。您的任务是分发公寓，以便有尽可能多的申请人获得公寓。

每个申请人都有所需的公寓面积，他们将接受任何尺寸足够接近所需尺寸的公寓。

输入

The first input line has three integers n, m, and k: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains n integers a1,a2,…,an: the desired apartment size of each applicant. If the desired size of an applicant is x, he or she will accept any apartment whose size is between x−k and x+k.

The last line contains m integers b1,b2,…,bm: the size of each apartment.

输出

Print one integer: the number of applicants who will get an apartment.

约束

1 ≤ n, m ≤ 2e5
0 ≤ k ≤ 1e9
1 ≤ ai, bi ≤ 1e9

我的尝试

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <utility>
typedef long long int ll;

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> vn, vm;
    for (int i = 0; i < n; i++)
    {
        int p;
        cin >> p;
        vn.push_back(p);
    }
    for (int i = 0; i < m; i++)
    {
        int p;
        cin >> p;
        vm.push_back(p);
    }
    int c = 0;
    sort(vn.begin(), vn.end());
    sort(vm.begin(), vm.end());
    for (int i = 0; i < m; i++)
    {

        for (int j = 0; j < vn.size(); j++)
        {
            if (vm[i] <= vn[j] + k && vm[i] >= vn[j] - k)
            {
                c++;
                vn.erase(vn.begin() + j);
                break;
            }
            if (vn[j] < vm[i] - k)
            {
                vn.erase(vn.begin() + j);
                j--;
                continue;
            }
            if (vn[j] > vm[i] + k)
            {
                break;
            }
        }
    }
    cout << c << "\n";
}

我在某些测试案例中超过了时间限制。

Answer 1

您的算法的时间复杂度是O（m * n ^ 2），尽管实际上我们可以说它是O（n ^ 3）。

供您参考，它是O（n ^ 3），因为您有两个for循环，创建了O（n ^ 2）的复杂性，但是在这些循环中，有一个函数调用std :: vector.erase（） ，擦除函数是线性运算O（n），因此我们将其乘以O（n ^ 2）并得到O（n ^ 3）的时间复杂度。如果您需要更多说明，请与我联系。

现在您是什么是理想的运行时的问题。显然，这是一个排序/搜索问题。我相信可以在O（n ^ 2）中完成。

我的解决方案：

按升序排列公寓的大小和所需的每个申请人。从最挑剔的“租户”开始，按顺序填充公寓，即最小的所需租户。注意，这是“ O（n ^ 2）”，但实际上比标准O（n ^ 2）算法快得多。

伪代码：

        int count = 0;
        vector<int> desired, apartments;
        //Fill these vectors
        //Sort the vectors
        for(int apt = 0; apt < apartments.size();apt++){
            for(int person = 0;person < desired.size();person++){
               if(canEnterApartment(desired.at(person),apartments.at(apt)){
                 count++;
                 //Remove all tenants before this
                 break;
               }
            }
         }
         return count;