发现从一组范围的最频繁的数字 - [英] Finding the most frequent number from a set of ranges -

问题描述

现在的问题如下： -

The question is as follows:-

您给出的N个不同的大象，psented为一对整数重新$ P $的续航时间。

You are given the life time of N different elephants, represented as a pair of integers.

恩。 [5,10] [6,15] [2,7] 手段，一是大象从居住5年至10年。第二，从生活6年至第15年等。

ex. [5,10] [6,15] [2,7] means, one elephant lived from Year 5 to Year 10. The second lived from Year 6 to Year 15 and so on..

您可能会认为大象只能活一个最大的并购年。 （这个问题不是一个组成部分，但我们可能需要重新present算法复杂度。）

You may assume that an elephant can only live a maximum of M years. (Not a part of the question, but we may need it to represent algorithmic complexity.)

鉴于这一数据，在其中找到大象的最大数量居住的年。 随意解决的联系。

Given this data, find the year in which the maximum number of elephants lived. Resolve ties arbitrarily.

我尝试了好几种方法来此，但没有实质性的似乎击败天真的解决方案的复杂性。天真的解决方案是： -

I have tried several approaches to this, but nothing substantial seems to beat the naive solution's complexity. The naive solution is:-

1. Maintain an array(call it ctr).
2. For every set you encounter, 
    increment all values of ctr in that range.
3. Once you have traversed all sets, 
    find the index with the highest value in ctr.

可以很容易地看到，复杂性将是O（N * M）。

It's easy to see that the complexity will be O(N*M).

任何人都可以提供一个更好的解决方案？

Can anyone offer a better solution?

这是另一种问题是：是否有一个数据结构，在其中您可以更改O（1）时间值的范围？在一个阵列，修改k个元素，你显然需要O（k）的时间。更好的东西？

An alternative question is: Is there a data structure in which you can change a range of values in O(1) time? In an array, to modify k elements, you clearly require O(k) time. Anything better?

推荐答案

想象范围为+1大象活着的左端，与范围右端为-1大象活着。放在一些行的+1和-1的标记，然后去按排序顺序从左向右数轴上。当你走数字路线，跟踪大象活着的电流数量（只添加了+1和-1的），并检查其对大象的生存与相应年份的最大数量。然后，你有一个很好的为O（n log n）的时间解决问题的办法。

Think of the left end of a range as +1 elephant alive, and the right end of range as -1 elephant alive. Put those +1 and -1 markers on a number line, and then go in sorted order from left to right on the number line. As you walk the number line, keep track of current number of elephants alive (just add up the +1 and -1s), and check it against the maximum number of elephants alive and corresponding year. Then you have a nice O(n log n) time solution to the problem.

请注意，你必须要小心一点与簿记前+ 1S处理-1s在本年度，或者只给你处理给定的一年中的所有数据后更新您的最大值。

Note that you have to be a little careful with the bookkeeping to handle -1s before +1s in the current year, or only to update your maximums after you process all the data within a given year.

这篇关于发现从一组范围的最频繁的数字 - 的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！