在范围数组中查找最大值
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 的解决方案更好,否则更糟。