[打卡]8.14_1583. 统计不开心的朋友

相关题解:统计不开心的朋友

image-20210814014513889

AC代码:

class Solution {
public:
    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
        vector<vector<int>> g(n, vector<int>(n));//创建一个二维数组,用于映射每个 i 的亲密度排列
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n - 1; j++)
                g[i][preferences[i][j]] = j;//按权重(亲密度)进行排列,下标作为权重使用

        vector<int> match(n);//配对数组
        for (auto& pr : pairs) {
            match[pr[0]] = pr[1];//将pairs中的配对信息映射到这个数组中 其中下标为x,值为y
            match[pr[1]] = pr[0];
        }
        int res = 0;
        for (int x = 0; x < n; x++) {//遍历每个人
            int y = match[x];//取x的配对
            int idx = g[x][y];//取x与y在g中的权重(亲密度)
            for (int i = 0; i < idx; i++) {//遍历比y权重高的
                int u = preferences[x][i];//取得权重比y高的编号
                int v = match[u];//取得这个编号的配对
                if (g[u][x] < g[u][v]) {//如果这个人与x的配对要高于这个人原本的配对,则这个人会不开心
                    res++;//我不开心
                    break;
                }
            }
        }
        return res;
    }
};

本文链接:

https://nullcode.fun/169.html
1 + 4 =
快来做第一个评论的人吧~