在范围数组中查找最大值
Find max value in an array of ranges
假设我有 1900 年到 2000 年间 100 个人的出生和死亡年份数组。
因此：
人[0][出生] = 1900;
人[0][死亡] = 1960;
.
.
.
人[99][出生] = 1904;
人[99][死亡] = 1982;
我想找出大多数人生活在这些范围之间的年份。
显而易见的方法是遍历每个人，计算他生活的年数（死亡 - 出生），然后使用内部循环将这些年数添加到累积数组中。运行时间为 O(n^2).
有没有更有效的方法来做到这一点？
创建一个存储一对数据（[出生或死亡]，年份）的数组。每个人都会创建两组这样的数据。这需要 O(n).
按年份对该数组进行排序。这需要 O(nlogn).
处理该数组并将当前存活的人数保持在一个变量中，相应地减少和增加。将最大数量存储到该点。这又需要 O(n).
示例：
A: 1904年生，1960年卒 B: 1930年生，1960年卒 C: 1940年生，1950年卒
-> 死亡和出生数组开始于 (birth, 1904), (death, 1960), ...
-> 数组排序：(birth, 1904), (birth, 1930), (birth 1940), (death, 1950), (death, 1960), (death, 1960)
-> 处理数组：1904年，1人存活。 1930 年，住着两个人。在...
O 符号有时可能有点误导。你没有只有一个变量。人数是n。设生命长度为y，整个区间Y。精确评估 您的解决方案不是 O(n^2)，而是 O(MAX(n*y, Y))。如果你说 Y 是 100 并且永远是，你的解决方案是 O(n)，因为 y<=Y 并且它们都作为常数被消除。你用两倍的人做两倍的工作，所以它真的是线性的，只是常数很高。打上O(n^2)严格来说就是生命的长短与人数成正比，这恐怕是无稽之谈。假设从现在开始，y 等于 Y。现在您的解决方案简化为 O(n*y).
你可以改进你的算法。将出生的 +1 和死亡的 -1 存储到累加数组中。每个人只有两个价值观。现在您可以通过该数组一次并获得每年居住的人数。时间将是 O(MAX(n, y))。当 n*log(n) 比 y 增长得更快时，它比 @Aziuth 的解决方案更好，否则更糟。
假设我有 1900 年到 2000 年间 100 个人的出生和死亡年份数组。
因此：
人[0][出生] = 1900;
人[0][死亡] = 1960;
.
.
.
人[99][出生] = 1904;
人[99][死亡] = 1982;
我想找出大多数人生活在这些范围之间的年份。
显而易见的方法是遍历每个人，计算他生活的年数（死亡 - 出生），然后使用内部循环将这些年数添加到累积数组中。运行时间为 O(n^2).
有没有更有效的方法来做到这一点？
创建一个存储一对数据（[出生或死亡]，年份）的数组。每个人都会创建两组这样的数据。这需要 O(n).
按年份对该数组进行排序。这需要 O(nlogn).
处理该数组并将当前存活的人数保持在一个变量中，相应地减少和增加。将最大数量存储到该点。这又需要 O(n).
示例： A: 1904年生，1960年卒 B: 1930年生，1960年卒 C: 1940年生，1950年卒
-> 死亡和出生数组开始于 (birth, 1904), (death, 1960), ...
-> 数组排序：(birth, 1904), (birth, 1930), (birth 1940), (death, 1950), (death, 1960), (death, 1960)
-> 处理数组：1904年，1人存活。 1930 年，住着两个人。在...
O 符号有时可能有点误导。你没有只有一个变量。人数是n。设生命长度为y，整个区间Y。精确评估 您的解决方案不是 O(n^2)，而是 O(MAX(n*y, Y))。如果你说 Y 是 100 并且永远是，你的解决方案是 O(n)，因为 y<=Y 并且它们都作为常数被消除。你用两倍的人做两倍的工作，所以它真的是线性的，只是常数很高。打上O(n^2)严格来说就是生命的长短与人数成正比，这恐怕是无稽之谈。假设从现在开始，y 等于 Y。现在您的解决方案简化为 O(n*y).
你可以改进你的算法。将出生的 +1 和死亡的 -1 存储到累加数组中。每个人只有两个价值观。现在您可以通过该数组一次并获得每年居住的人数。时间将是 O(MAX(n, y))。当 n*log(n) 比 y 增长得更快时，它比 @Aziuth 的解决方案更好，否则更糟。