Question

1854. 人口最多的年份

English Version

题目描述

给你一个二维整数数组 logs ，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足：x 在闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口中。

返回 人口最多 且 最早 的年份。

 

示例 1：

输入：logs = [[1993,1999],[2000,2010]]
输出：1993
解释：人口最多为 1 ，而 1993 是人口为 1 的最早年份。

示例 2：

输入：logs = [[1950,1961],[1960,1971],[1970,1981]]
输出：1960
解释： 
人口最多为 2 ，分别出现在 1960 和 1970 。
其中最早年份是 1960 。

 

提示：

• 1 <= logs.length <= 100
• 1950 <= birthi < deathi <= 2050

解法

方法一：差分数组

我们注意到，年份的范围是 $[1950,..2050]$，因此我们可以将这些年份映射到一个长度为 $101$ 的数组 $d$ 中，数组的下标表示年份减去 $1950$ 的值。

接下来遍历 $logs$，对于每个人，我们将 $d[birth_i - 1950]$ 加 $1$，将 $d[death_i - 1950]$ 减 $1$。最后遍历数组 $d$，求出前缀和的最大值，即为人口最多的年份，再加上 $1950$ 即为答案。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为数组 $logs$ 的长度；而 $C$ 为年份的范围大小，即 $2050 - 1950 + 1 = 101$。

class Solution:
  def maximumPopulation(self, logs: List[List[int]]) -> int:
    d = [0] * 101
    offset = 1950
    for a, b in logs:
      a, b = a - offset, b - offset
      d[a] += 1
      d[b] -= 1
    s = mx = j = 0
    for i, x in enumerate(d):
      s += x
      if mx < s:
        mx, j = s, i
    return j + offset

class Solution {
  public int maximumPopulation(int[][] logs) {
    int[] d = new int[101];
    final int offset = 1950;
    for (var log : logs) {
      int a = log[0] - offset;
      int b = log[1] - offset;
      ++d[a];
      --d[b];
    }
    int s = 0, mx = 0;
    int j = 0;
    for (int i = 0; i < d.length; ++i) {
      s += d[i];
      if (mx < s) {
        mx = s;
        j = i;
      }
    }
    return j + offset;
  }
}

class Solution {
public:
  int maximumPopulation(vector<vector<int>>& logs) {
    int d[101]{};
    const int offset = 1950;
    for (auto& log : logs) {
      int a = log[0] - offset;
      int b = log[1] - offset;
      ++d[a];
      --d[b];
    }
    int s = 0, mx = 0;
    int j = 0;
    for (int i = 0; i < 101; ++i) {
      s += d[i];
      if (mx < s) {
        mx = s;
        j = i;
      }
    }
    return j + offset;
  }
};

func maximumPopulation(logs [][]int) int {
  d := [101]int{}
  offset := 1950
  for _, log := range logs {
    a, b := log[0]-offset, log[1]-offset
    d[a]++
    d[b]--
  }
  var s, mx, j int
  for i, x := range d {
    s += x
    if mx < s {
      mx = s
      j = i
    }
  }
  return j + offset
}

function maximumPopulation(logs: number[][]): number {
  const d: number[] = new Array(101).fill(0);
  const offset = 1950;
  for (const [birth, death] of logs) {
    d[birth - offset]++;
    d[death - offset]--;
  }
  let j = 0;
  for (let i = 0, s = 0, mx = 0; i < d.length; ++i) {
    s += d[i];
    if (mx < s) {
      mx = s;
      j = i;
    }
  }
  return j + offset;
}

/**
 * @param {number[][]} logs
 * @return {number}
 */
var maximumPopulation = function (logs) {
  const d = new Array(101).fill(0);
  const offset = 1950;
  for (let [a, b] of logs) {
    a -= offset;
    b -= offset;
    d[a]++;
    d[b]--;
  }
  let j = 0;
  for (let i = 0, s = 0, mx = 0; i < 101; ++i) {
    s += d[i];
    if (mx < s) {
      mx = s;
      j = i;
    }
  }
  return j + offset;
};