No.1583 统计不开心的朋友

给你一份 n 位朋友的亲近程度列表，其中 n 总是偶数。

对每位朋友 i，preferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。换句话说，排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。每个列表中的朋友均以 0 到 n-1 之间的整数表示。

所有的朋友被分成几对，配对情况以列表 pairs 给出，其中 pairs[i] = [x_i, y_i] 表示 x_i 与 y_i 配对，且 y_i 与 x_i 配对。

但是，这样的配对情况可能会是其中部分朋友感到不开心。在 x 与 y 配对且 u 与 v 配对的情况下，如果同时满足下述两个条件，x 就会不开心：

x 与 u 的亲近程度胜过 x 与 y，且
u 与 x 的亲近程度胜过 u 与 v

返回 不开心的朋友的数目 。

示例 1：

输入：n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
输出：2
解释：
朋友 1 不开心，因为：
- 1 与 0 配对，但 1 与 3 的亲近程度比 1 与 0 高，且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心，因为：
- 3 与 2 配对，但 3 与 1 的亲近程度比 3 与 2 高，且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。

示例 2：

输入：n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
输出：0
解释：朋友 0 和 1 都开心。

示例 3：

输入：n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
输出：4

提示：

2 <= n <= 500
n 是偶数
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] 不包含 i
preferences[i] 中的所有值都是独一无二的
pairs.length == n/2
pairs[i].length == 2
x_i != y_i
0 <= x_i, y_i <= n - 1
每位朋友都恰好被包含在一对中

思路分析

首先我们要对给入的数据做一个预处理，因为我们在查询亲近程度的时候一定是希望给进两个人，给出一个亲近程度的指数。而题目给我们的数据非常不直观。所以我们可以拿一个二维数组来重新装一下。

let n = 10;
let preferences = vec![vec![3]];
let n = n as usize;
let mut pre = vec![vec![0; n]; n];
for i in 0..n {
    for j in 0..(n - 1) {
        pre[i][preferences[i][j] as usize] = n - j - 1;
    }
}

以上代码将preferences重新整合至pre。这样我们就能很方便的通过pre[i][j]的方式来查询了。

接下来我们仔细观察不开心的示例并且将其改写为代码
pre[x][u] > pre[x][y] && pre[u][x] > pre[u][v]
这个式子非常有意思，不难看出，在满足这个式子的时候，不仅x不满意，u也不满意。
再进一步观察又能发现，这个式子通过x和u是可以完全确定的。所以对于x,y,u,v四个变量来说，这样的两两组合一共有四对。

let (a, b, c, d) = (0, 0, 0, 0);
let pre = vec![vec![3]];
let mut set = std::collections::HashSet::new();
if pre[a][c] > pre[a][b] && pre[c][a] > pre[c][d] {
    set.insert(a);
    set.insert(c);
}
if pre[b][c] > pre[b][a] && pre[c][b] > pre[c][d] {
    set.insert(b);
    set.insert(c);
}
if pre[b][d] > pre[b][a] && pre[d][b] > pre[d][c] {
    set.insert(b);
    set.insert(d);
}
if pre[d][a] > pre[d][c] && pre[a][d] > pre[a][b] {
    set.insert(d);
    set.insert(a);
}

其中set是为了不重复而设置的哈希集合。（x,y,u,v为了方便写成了a,b,c,d）然后再对哈希表进行遍历并输出即可。

Rust代码


#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn unhappy_friends(n: i32, preferences: Vec<Vec<i32>>, pairs: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut pre = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..(n - 1) {
                pre[i][preferences[i][j] as usize] = n - j - 1;
            }
        }
        // println!("{:?}", pre);
        use std::collections::*;
        let mut set = HashSet::new();
        for i in 0..pairs.len() {
            for j in 0..pairs.len() {
                let a = pairs[i][0] as usize;
                let b = pairs[i][1] as usize;
                let c = pairs[j][0] as usize;
                let d = pairs[j][1] as usize;
                if pre[a][c] > pre[a][b] && pre[c][a] > pre[c][d] {
                    set.insert(a);
                    set.insert(c);
                }
                if pre[b][c] > pre[b][a] && pre[c][b] > pre[c][d] {
                    set.insert(b);
                    set.insert(c);
                }
                if pre[b][d] > pre[b][a] && pre[d][b] > pre[d][c] {
                    set.insert(b);
                    set.insert(d);
                }
                if pre[d][a] > pre[d][c] && pre[a][d] > pre[a][b] {
                    set.insert(d);
                    set.insert(a);
                }
            }
        }
        set.len() as i32
    }
}
}

LeetCode Solution - 力扣题解

No.1583 统计不开心的朋友

思路分析

Rust代码