This is the 14th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

Leetcode -1583- Count unhappy friends

[Blog link]

The way to study ๐Ÿ”

The nuggets home page

[Topic description]

I give you a list of the closeness of n friends, where n is always even.

For each friend I, Preferences [I] contain a list of friends ranked from most to least close. In other words, friends at the top of the list were closer to I than friends at the bottom. Each list of friends is represented as an integer between 0 and N-1.

All the friends are split into pairs and matched as a list of pairs, with pairs[I] = [xi, yi] indicating that Xi pairs with Yi, and yi pairs with Xi.

However, such a pairing may make some friends unhappy. If x is paired with y and U is paired with V, x will be unhappy if both of the following conditions are met:

X is closer to u than x is to y and u is closer to x than u is to V

Returns the number of unhappy friends.

Example 1:

Input: n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]] output: 2: friends 1 unhappy, because: -1 is paired with 0, but 1 and 3 are closer than 1 and 0, and -3 is closer to 1 than 3 and 2. Friend 3 is unhappy because: -3 is paired with 2, but 3 is closer to 1 than 3 is to 2, and -1 is closer to 3 than 1 is to 0. Friends 0 and 2 are happy.Copy the code

Example 2:

Input: n = 2, Preferences = [[1], [0]], pairs = [[1, 0]] Output: 0 Explanation: Friends 0 and 1 are happy.Copy the code

Example 3:

Input: n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0] to [0, 2, 1]], pairs = [[1, 3], [0, 2]] output: 4Copy the code

Tip:

  • 2 <= n <= 500
  • N is an even number
  • preferences.length == n
  • preferences[i].length == n – 1
  • 0 <= preferences[i][j] <= n – 1
  • Preferences [I] Does not contain I
  • All values in Preferences [I] are unique
  • pairs.length == n/2
  • pairs[i].length == 2
  • xi ! = yi
  • 0 <= xi, yi <= n – 1
  • Each friend happens to be included in a pair

Related Topics

  • An array of
  • simulation
  • ๐Ÿ‘ 22 ๐Ÿ‘Ž 0

[Topic link]

Leetcode title link

[making address]

Code link

[ๆ€่ทฏไป‹็ป]

Idea 1: Simulate arrays

  • Scan preference for each array element separately
  • Dis [I][J] indicates the distance between two nodes (definition of intimacy)
  • Because the questions are so restrictive (you can’t repeat and increase), you can use subscripts to indicate closeness
  • In preference[I], the distance of each element in preference[I][j] is represented by j
  • Dis [I][preference[I][j]] = j
  • And then we go through the for loop twice
  • The unhappy node is recorded through the set
  • The for loop defines two coordinate points [x,y] and [u,v] respectively
  • Determine the size of dis[x/y][U /v]
  • The number of sets is returned
  • Finally this question Tanabata is really a killer
  • It’s too late today. Happy Chinese Valentine’s Day
public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
    Set<Integer> unhappy = new HashSet<>();
    int[][] dis = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) { dis[i][preferences[i][j]] = j; }}int x = 0, y = 0, u = 0, v = 0;
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < pairs.length; j++) {
            if (j == i) {
                continue;
            }
            x = pairs[i][0];
            y = pairs[i][1];
            u = pairs[j][0];
            v = pairs[j][1];
            if (dis[x][u] < dis[x][y] && dis[u][x] < dis[u][v]) {
                unhappy.add(x);
            }
            if (dis[x][v] < dis[x][y] && dis[v][x] < dis[v][u]) {
                unhappy.add(x);
            }
            if (dis[y][u] < dis[y][x] && dis[u][y] < dis[u][v]) {
                unhappy.add(y);
            }
            if(dis[y][v] < dis[y][x] && dis[v][y] < dis[v][u]) { unhappy.add(y); }}}return unhappy.size();
}
Copy the code
  • Time complexity O(
    n 2 n^{2}     )
  • Space complexity O(
    n 2 n^{2}     )