Question

1101. 彼此熟识的最早时间

English Version

题目描述

在一个社交圈子当中，有 n 个人。每个人都有一个从 0 到 n - 1 的唯一编号。我们有一份日志列表 logs，其中 logs[i] = [timestampi, xi, yi] 表示 xi 和 yi 将在同一时间 timestampi 成为朋友。

友谊是 相互 的。也就是说，如果 a 和 b 是朋友，那么 b 和 a 也是朋友。同样，如果 a 和 b 是朋友，或者 a 是 b 朋友的朋友 ，那么 a 和 b 是熟识友。

返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间，就返回 -1 。

 

示例 1：

输入：logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6
输出：20190301
解释：
第一次结交发生在 timestamp = 20190101，0 和 1 成为好友，社交朋友圈如下 [0,1], [2], [3], [4], [5]。
第二次结交发生在 timestamp = 20190104，3 和 4 成为好友，社交朋友圈如下 [0,1], [2], [3,4], [5].
第三次结交发生在 timestamp = 20190107，2 和 3 成为好友，社交朋友圈如下 [0,1], [2,3,4], [5].
第四次结交发生在 timestamp = 20190211，1 和 5 成为好友，社交朋友圈如下 [0,1,5], [2,3,4].
第五次结交发生在 timestamp = 20190224，2 和 4 已经是好友了。
第六次结交发生在 timestamp = 20190301，0 和 3 成为好友，大家都互相熟识了。

示例 2:

输入: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
输出: 3

 

提示：

• 2 <= n <= 100
• 1 <= logs.length <= 104
• logs[i].length == 3
• 0 <= timestampi <= 109
• 0 <= xi, yi <= n - 1
• xi != yi
• timestampi 中的所有时间戳 均不同
• 所有的对 (xi, yi) 在输入中最多出现一次

解法

方法一：排序 + 并查集

我们将所有的日志按照时间戳从小到大排序，然后遍历排序后的日志，利用并查集判断当前日志中的两个人是否已经是朋友，如果不是朋友，则将两个人合并成一个朋友圈，直到所有人都在一个朋友圈中，返回当前日志的时间戳。

如果遍历完所有日志，还没有所有人都在一个朋友圈中，则返回 $-1$。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为日志的数量。

class Solution:
  def earliestAcq(self, logs: List[List[int]], n: int) -> int:
    def find(x):
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    p = list(range(n))
    for t, x, y in sorted(logs):
      if find(x) == find(y):
        continue
      p[find(x)] = find(y)
      n -= 1
      if n == 1:
        return t
    return -1

class Solution {
  private int[] p;

  public int earliestAcq(int[][] logs, int n) {
    Arrays.sort(logs, (a, b) -> a[0] - b[0]);
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    for (int[] log : logs) {
      int t = log[0], x = log[1], y = log[2];
      if (find(x) == find(y)) {
        continue;
      }
      p[find(x)] = find(y);
      if (--n == 1) {
        return t;
      }
    }
    return -1;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

class Solution {
public:
  int earliestAcq(vector<vector<int>>& logs, int n) {
    sort(logs.begin(), logs.end());
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) {
      return p[x] == x ? x : p[x] = find(p[x]);
    };
    for (auto& log : logs) {
      int x = find(log[1]);
      int y = find(log[2]);
      if (x != y) {
        p[x] = y;
        --n;
      }
      if (n == 1) {
        return log[0];
      }
    }
    return -1;
  }
};

func earliestAcq(logs [][]int, n int) int {
  sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
  p := make([]int, n)
  for i := range p {
    p[i] = i
  }
  var find func(int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  for _, log := range logs {
    t, x, y := log[0], log[1], log[2]
    if find(x) == find(y) {
      continue
    }
    p[find(x)] = find(y)
    n--
    if n == 1 {
      return t
    }
  }
  return -1
}

function earliestAcq(logs: number[][], n: number): number {
  const p: number[] = Array(n)
    .fill(0)
    .map((_, i) => i);
  const find = (x: number): number => {
    if (p[x] !== x) {
      p[x] = find(p[x]);
    }
    return p[x];
  };
  logs.sort((a, b) => a[0] - b[0]);
  for (const [t, x, y] of logs) {
    const rx = find(x);
    const ry = find(y);
    if (rx !== ry) {
      p[rx] = ry;
      if (--n === 1) {
        return t;
      }
    }
  }
  return -1;
}

struct UnionFind {
  p: Vec<usize>,
  size: Vec<usize>,
}

impl UnionFind {
  fn new(n: usize) -> Self {
    let p: Vec<usize> = (0..n).collect();
    let size = vec![1; n];
    UnionFind { p, size }
  }

  fn find(&mut self, x: usize) -> usize {
    if self.p[x] != x {
      self.p[x] = self.find(self.p[x]);
    }
    self.p[x]
  }

  fn union(&mut self, a: usize, b: usize) -> bool {
    let pa = self.find(a);
    let pb = self.find(b);
    if pa == pb {
      false
    } else if self.size[pa] > self.size[pb] {
      self.p[pb] = pa;
      self.size[pa] += self.size[pb];
      true
    } else {
      self.p[pa] = pb;
      self.size[pb] += self.size[pa];
      true
    }
  }
}

impl Solution {
  pub fn earliest_acq(logs: Vec<Vec<i32>>, n: i32) -> i32 {
    let mut logs = logs;
    logs.sort_by(|a, b| a[0].cmp(&b[0]));
    let mut uf = UnionFind::new(n as usize);
    let mut n = n;
    for log in logs {
      let t = log[0];
      let x = log[1] as usize;
      let y = log[2] as usize;
      if uf.union(x, y) {
        n -= 1;
        if n == 1 {
          return t;
        }
      }
    }
    -1
  }
}

方法二

class UnionFind:
  __slots__ = ('p', 'size')

  def __init__(self, n):
    self.p = list(range(n))
    self.size = [1] * n

  def find(self, x: int) -> int:
    if self.p[x] != x:
      self.p[x] = self.find(self.p[x])
    return self.p[x]

  def union(self, a: int, b: int) -> bool:
    pa, pb = self.find(a), self.find(b)
    if pa == pb:
      return False
    if self.size[pa] > self.size[pb]:
      self.p[pb] = pa
      self.size[pa] += self.size[pb]
    else:
      self.p[pa] = pb
      self.size[pb] += self.size[pa]
    return True


class Solution:
  def earliestAcq(self, logs: List[List[int]], n: int) -> int:
    uf = UnionFind(n)
    for t, x, y in sorted(logs):
      if uf.union(x, y):
        n -= 1
        if n == 1:
          return t
    return -1

class UnionFind {
  private int[] p;
  private int[] size;

  public UnionFind(int n) {
    p = new int[n];
    size = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      size[i] = 1;
    }
  }

  public int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }

  public boolean union(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) {
      return false;
    }
    if (size[pa] > size[pb]) {
      p[pb] = pa;
      size[pa] += size[pb];
    } else {
      p[pa] = pb;
      size[pb] += size[pa];
    }
    return true;
  }
}

class Solution {
  public int earliestAcq(int[][] logs, int n) {
    Arrays.sort(logs, (a, b) -> a[0] - b[0]);
    UnionFind uf = new UnionFind(n);
    for (int[] log : logs) {
      int t = log[0], x = log[1], y = log[2];
      if (uf.union(x, y) && --n == 1) {
        return t;
      }
    }
    return -1;
  }
}

class UnionFind {
public:
  UnionFind(int n) {
    p = vector<int>(n);
    size = vector<int>(n, 1);
    iota(p.begin(), p.end(), 0);
  }

  bool unite(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) {
      return false;
    }
    if (size[pa] > size[pb]) {
      p[pb] = pa;
      size[pa] += size[pb];
    } else {
      p[pa] = pb;
      size[pb] += size[pa];
    }
    return true;
  }

  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }

private:
  vector<int> p, size;
};

class Solution {
public:
  int earliestAcq(vector<vector<int>>& logs, int n) {
    sort(logs.begin(), logs.end());
    UnionFind uf(n);
    for (auto& log : logs) {
      int t = log[0], x = log[1], y = log[2];
      if (uf.unite(x, y) && --n == 1) {
        return t;
      }
    }
    return -1;
  }
};

type unionFind struct {
  p, size []int
}

func newUnionFind(n int) *unionFind {
  p := make([]int, n)
  size := make([]int, n)
  for i := range p {
    p[i] = i
    size[i] = 1
  }
  return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
  if uf.p[x] != x {
    uf.p[x] = uf.find(uf.p[x])
  }
  return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
  pa, pb := uf.find(a), uf.find(b)
  if pa == pb {
    return false
  }
  if uf.size[pa] > uf.size[pb] {
    uf.p[pb] = pa
    uf.size[pa] += uf.size[pb]
  } else {
    uf.p[pa] = pb
    uf.size[pb] += uf.size[pa]
  }
  return true
}

func earliestAcq(logs [][]int, n int) int {
  sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
  uf := newUnionFind(n)
  for _, log := range logs {
    t, x, y := log[0], log[1], log[2]
    if uf.union(x, y) {
      n--
      if n == 1 {
        return t
      }
    }
  }
  return -1
}

class UnionFind {
  private p: number[];
  private size: number[];

  constructor(n: number) {
    this.p = Array(n)
      .fill(0)
      .map((_, i) => i);
    this.size = Array(n).fill(1);
  }

  find(x: number): number {
    if (this.p[x] !== x) {
      this.p[x] = this.find(this.p[x]);
    }
    return this.p[x];
  }

  union(a: number, b: number): boolean {
    const pa = this.find(a);
    const pb = this.find(b);
    if (pa === pb) {
      return false;
    }
    if (this.size[pa] > this.size[pb]) {
      this.p[pb] = pa;
      this.size[pa] += this.size[pb];
    } else {
      this.p[pa] = pb;
      this.size[pb] += this.size[pa];
    }
    return true;
  }
}

function earliestAcq(logs: number[][], n: number): number {
  logs.sort((a, b) => a[0] - b[0]);
  const uf = new UnionFind(n);
  for (const [t, x, y] of logs) {
    if (uf.union(x, y) && --n === 1) {
      return t;
    }
  }
  return -1;
}