Блог

У меня есть два отсортированных массива временных меток unix (таким образом, целые числа, представляющие время, в которое происходят некоторые события). Давайте вызовем массивы ts1 и ts2. Я хочу найти количество событий в ts1, которые происходят после w минут любого события в ts2. Допустим, сигнатура метода такова (берем первый и второй массивы и размер окна, затем возвращаем количество событий в ts1, которые произошли в течение w минут после любого события в ts2):

 critical_events(ts1,ts2,w)->int
  

Вот несколько тестовых примеров:

 ## Test cases.
ev = critical_events([.5,1.5,2.5],[1,2,3],.5)
print(ev==0)

ev = critical_events([1.4,1.4,2.7],[1,2,3],.5)
print(ev==2)

ev = critical_events([1.4,2.4,3.4],[1,2,3],.5)
print(ev==3)
  

Я ожидаю, что длина первого массива, n, будет намного больше длины второго, m. Ищу эффективные алгоритмы с точки зрения времени и пространства и, если возможно, их среднюю и наихудшую сложность с точки зрения n и m, времени и пространства.

Моя попытка: вместо объяснения моих попыток я просто дам ссылку на код, который должен быть понятным (или, по крайней мере, лучше того, что я могу сделать словами): https://gist.github.com/ryu577/fdc22af4ed17d122a6aa25684597745b

Вы показываете их отсортированными, поэтому я предполагаю, что так оно и есть (должно быть, чтобы это сработало). Поскольку ваш первый массив намного больше второго, вам нужно использовать второй в цикле for.

Я использую примерный тестовый пример 2: ev = critical_events([1.4,1.4,2.7],[1,2,3], . 5) Далее вы можете использовать двоичный поиск по первому элементу ts2 интервал (1 0,5) = 1,5.

Ваш startIndex равен 0, а endIndex равен 2. Итак, при первом сравнении вы берете все элементы.

Выполнение двоичного поиска приведет к индексу 2 в ts1. Примечание: Поскольку у вас в массиве одинаковый элемент, вам нужно двигаться вправо, пока не получите большее число. Теперь вы можете сказать, что 2.7 (и все элементы после, если таковые имеются) — это элемент, который находится после 1.5. Count равен ts2.length — foundindex.

Теперь вы можете установить свой начальный индекс равным 2. потому что вы знаете, что все слева от этого индекса меньше и не будут лежать через 1,5 секунды. Вы берете элемент2 и выполняете двоичный поиск, вы снова найдете индекс 2 ( 2.5 < 2.7):

Count = Количество ts2.длина — найденный индекс.

Насколько мне известно, это самый быстрый метод. Я полагаю, что скорость равна Log (n).m.