Krammer's blog

原題: https://leetcode.com/problems/count-unhappy-friends/ from Bloomberg

題目基本上就是給你朋友互相之間的preference，像

[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]]

接著再給你已配對好的朋友

[[0, 1], [2, 3]]

這時候要算出不高興的人有哪些。在這個例子中1跟3不高興，因為跟1配對的是0，但1比較喜歡3，且3的配對是2，但3也比較喜歡1，所以1跟3都不高興。

這裡還是一樣給出比賽時的寫法不做任何優化。主要的解法就是，先建立一個雙向的連結，好讓我知道任意一個人的好友是誰。接著，我們用一個rank array去記錄每個人喜歡的排序，比如說，2喜歡的順序是3,1,0，所以我們在rank[2]裡3排第0，1排第1，0排最後(第2)，所以rank[2]就會是[2,1,0]。有了這個vector，在我們要計算誰的preference比較靠前的時候就可以快速很多，不用在重跑一遍preference array。

最後一段基本上就是照題目說的一個一個確認。舉例來說，當我們檢查第一對[0,1]的時候，我們先確認0，0的第一preference就是1了，所以不用再確認下去。而另一個人1也要做確認，1的preference是[3,2,0]，所以我們需要確認3跟2看是不是符合條件，從我們的map知道3的朋友是2，再從3的rank ([2,0,1]) 知道，2的rank比1差(數字比較大)，所以我們可以知道1比較想跟3配對，而3也比較想跟1配對，所以1跟3都不開心。

 1class Solution {
 2public:
 3    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
 4        unordered_map<int, int> mp;
 5        for (auto p : pairs) {
 6            mp[p[0]] = p[1];
 7            mp[p[1]] = p[0];
 8        }
 9        vector<vector<int>> rank(n, vector<int>(n));
10        for (int i=0; i<n; i++) {
11            for (int j=0; j<n-1; j++) {
12                rank[i][preferences[i][j]] = j;
13            }
14        }
15        set<int> ans;
16        for (auto p : pairs) {
17            for (auto f : preferences[p[0]]) {
18                if (f == p[1]) break;
19                if (mp.count(f)) {
20                    if (rank[f][p[0]] < rank[f][mp[f]])
21                        ans.insert(p[0]);
22                }
23            }
24            for (auto f : preferences[p[1]]) {
25                if (f == p[0]) break;
26                if (mp.count(f)) {
27                    if (rank[f][p[1]] < rank[f][mp[f]])
28                        ans.insert(p[1]);
29                }
30            }
31        }
32        return ans.size();
33    }
34};

Editorial: LeetCode 1583 Count Unhappy Friends