题解 | #算法交流群#

思路

题目分析

1. 本题给出了四组数据，分别来解释一下他们的含义：
   1. 第一项表示一共有多少人
   2. 第二项表示这些人的做出题目的等级能力，按序为第1人，第2人...第n人
   3. 第三项表示除了第1人之外，第2人，第3人...第n人会求助的人
   4. 第四项表示这些人产生问题的难度，按序为第1人，第2人...第n人的问题难度

• 我们首先可以尝试遍历所有人，让每个人都去处理自己的问题，然后其中有人无法解决自己的问题的时候尝试一步步交给上一个人做，直到该问题被解决。这种方法就是暴力解法，时间复杂度大概在左右
• 因此我们可以优化的部分就是在向上递交问题解决的过程，我们不采用逐级递交问题的办法，而是采用以的量级向等级更高的人递交问题。
  • 我们可以选择递交给我们最近的上一级来帮助我们解决问题，这就是求助即上1级的人，但是上1级的人可能也无法解决我们的问题，他还要继续上交问题，所以这个点是暴力解法中较为消耗时间的点。所以我们也可以直接求助级别的人，跳级去求助，然后逐渐缩小这个求助的尺度逼近最先能解决这个问题等级的人
• 因此我们要精心设计一个具有这种性质的二维数组来存储每个人在遇到无法解决的问题时需要求助的方向和求助的跨级别程度。具体设计参考方法的详细介绍

方法一：暴力解法

• 其他人的暴力解法思路比较清楚可以参考，就是按照员工数组的顺序处理问题，难度大的问题进行循环或递归上交并逐步解决。
• 我这里多做了一个排序处理，优先处理等级最低能力最差的人的问题，他产生的问题上交，这样有序处理起来比普通暴力可以减小一定程度的时间开销。

• 首先手动写了一个快速排序算法，整理出来一个按照a数组中人员从小到大等级排序的一个a的索引数组（注意是索引），办法就是在对a数组进行快速排序的同时，对索引b数组进行同样的操作，最终返回b的索引数组
• 然后通过从最低等级的人开始，处理问题并将遗留提交给高等级的人，按照等级从小到大的顺序排查所有人并记录他们所解决的问题数量，返回最终的数组。

#include <numeric>
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 算法交流群
     * @param n int整型 群员个数
     * @param a int整型vector 群员的等级
     * @param p int整型vector 群友寻求帮助的人
     * @param k int整型vector 群友产生的问题等级
     * @return int整型vector
     */
    void quick_sort(vector<int>& a, vector<int>& b, int l, int r) {
        if(l < r) {
            swap(a[l], a[(l+r)/2]);
            swap(b[l], b[(l+r)/2]);
            int i = l;
            int j = r;
            int x = a[l];                            // 选取pivot
            int y = b[l];
            while (i < j) {
                while (i < j && a[j] >= x) j--;
                if (i < j) {                         // 如果右指针对应数字小于pivot则覆盖左指针对应数字（pivot已经保存）
                    a[i] = a[j];
                    b[i] = b[j];
                    i++;
                }
                while (i < j && a[i] < x) i++;
                if (i < j) {                        // 如果左指针对应数字大于pivot则覆盖右指针对应数字（右指针对应数字已覆盖到左侧）
                    a[j] = a[i];
                    b[j] = b[i];
                    j--;
                }
            }
            a[i] = x;                                //恢复pivot
            b[i] = y;
            quick_sort(a, b, l, i-1);                //递归排序pivot左侧
            quick_sort(a, b, i+1, r);                //递归排序pivot右侧
        }
    }

    // 输入人员数组a，输出按照人员等级排序的a的索引数组
    vector<int> sort_index(vector<int> arr) {
        vector<int> idx(arr.size());
        std::iota(idx.begin(),idx.end(),0);
        quick_sort(arr, idx, 0, arr.size()-1);
        return idx;
    }

    vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k) {
        // write code here    
        vector<int> idx = sort_index(a);                // 按照a中人员等级顺序排序的a的索引数组
        vector<vector<int>> ak;                         // 按照等级排序的人员应该处理的问题，其中ak[0]表示等级最低的人应该处理的问题数组

        // 构造ak数组
        for(int i = 0; i < a.size(); i++) {
            vector<int> ques;
            ques.push_back(k[idx[i]]);
            ak.push_back(ques);
        }
        ak.push_back({});                                // 多填充一个空的为了方便处理边界问题（方便处理牛牛有问题无法解决时向上递交的问题）
        // 最终的结果数组
        vector<int> res(a.size(), 0);
        //处理问题并向上级递交问题
        for(int i = 0; i < ak.size() - 1; i++) {
            int ability = a[idx[i]];                    // 表示当前人员的等级
            int next = ak.size()-1;                     // next表示当前人员会求助的下一位人员所在ak数组的哪一行
            if(idx[i]-1 >= 0) {                         // 定位下一位人员具体在ak数组的哪一行
                next = p[idx[i]-1]-1;
                vector<int>::iterator it = find(idx.begin(), idx.end(), next);
                next = it-idx.begin();
            }

            int solved = 0;
            for(int j = 0; j < ak[i].size(); j++) {
                if(ak[i][j] > ability) {
                    ak[next].push_back(ak[i][j]);    //解决不了的问题给下一位
                }
                else{
                    solved++;                        //解决了的问题计数
                }
            }
            res[idx[i]] = solved;                    //最终存储问题计数到res数组中
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：，因为问题是逐步递交的，所以遍历所有人是一重循环，每个人要遍历自己所遇到的所有问题是第二重循环。
• 空间复杂度：，利用ak数组存储人员+问题的二维信息，这是空间开销最大的部分

方法二：优化递交过程（所谓的树的方法）

• 其他解法中所描述到的关于树的思路，其实就是将这种跳级递交问题的思路类比成树的概念，才有了二分的类比。其实树不树的不重要，因为解决这个问题并没有很完全地利用到树的很多性质，最重要的思路还是这个跳级递交问题的思路。
• 我们以f[u][i]表示，在这个人无法解决自己的问题之后，他会寻求f[u][i]这个人的帮助，而f[u][i]是这个人的上级别的人（具体意思是如果寻求他的上一级进行帮助记为1次寻求，而寻求记为2次寻求，则f[u][i]这个人就是进行了次寻求找到的请求帮助的人）
• 因此我们要打造一个f[u][i]矩阵，其中就要递归地建立上下级的关系。最终利用这个矩阵进行问题求解，将向上递交问题这个过程优化到的水平（因为毕竟是级别的优化）
  

  class Solution {
  public:
    void buildf(int u, vector<vector<int>>& child, vector<vector<int>>& f){ //建立二维数组
        for(int i = 0; i < 19; i++) 
            f[u][i + 1] = f[f[u][i]][i];             //这里由于赋值中一直在嵌套，所以已经是按照指数级增长进行上级的赋值了
        for(int i = 0; i < child[u].size(); i++)
            buildf(child[u][i], child, f);              //对所有的下级进行同样操作
    }
    vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k) {
        vector<int> num(n, 0);
        vector<vector<int> > f(n + 1, vector<int>(20)); //最多2^19层
        vector<vector<int> > child(n + 1);   // child[1]表示1会直接帮助child[1]
        for(int i = 0; i < n-1 ; i++)        // 首先建立一级的帮助关系（2^0=1）
        {
            f[i + 2][0] = p[i];
            child[p[i]].push_back(i + 2);
        }
        buildf(1, child, f);                    // 递归建立二维数组
        if(k[0] <= a[0])                     // 牛牛（最高能力者）先处理自己的问题
        {
            num[0]++;
        }
        for(int i = 1; i < n; i++)           // 其余的人开始对问题处理
        { 
            if(k[i] <= a[i])                 // 结点i可以自己解决问题
            { 
                num[i]++; 
                continue;
            }
            int u = i + 1;                   // 获取当前人员的编号（编号和索引正好差1）
            for(int j = 18; j >= 0; j--)     // 向上二分查找
            { 
                if(f[u][j] == 0)             // 跨度太大了，一次就找到了最高的牛牛，需要调整j值
                {
                    continue;
                }
                int t = f[u][j];             // 缩小向上找的等级，直到其率先找到的不是牛牛
                if(k[i] > a[t - 1])          // 尝试让找到的人解决问题，如果问题不难，则随着j的继续减小缩小u向上找的尺度
                {                            
                    u = t;                   // 如果问题仍难，则更新为现在这个人继续找上级
                }
            }    
            u = f[u][0];                     // 找到了应该解决问题的最近的一级的人
            if(u == 0)                       // 最上级，如果牛牛也不能解决问题
                continue;
            else num[u - 1]++; 
        }
        return num;
    }
  };

复杂度分析

• 时间复杂度：，优化了向上寻求帮助后的时间复杂度。
• 空间复杂度：，buildf的递归空间消耗。