Лучшая структура данных для эффективного поиска интервалов с высокой плотностью

Question

У меня есть несортированный набор целых чисел и длина интервала. Мне нужно найти наибольшее подмножество элементов, включенных в заданный интервал

Пример 1:

Set: [11, 1, 2, 100, 12, 14, 99]

Interval: 4

Result: [11, 12, 14]

Пример 2:

Set: [1, 100, 55, 2, 88, 3]

Interval: 10

Result: [1, 2, 3]

На практике существует много больше элементов в наборе

Какова эффективная структура данных и алгоритм решения этой задачи?

Answer 1

1. Сортировка набора целых чисел в массив A и пусть w будет шириной нашего интервала.

2. Initialize i = j = best_start = best_n = 0.

3. Приращение j до A[j] < A[i] + w (или <= в зависимости от того, как вы определяете интервал).

4. Если j - i > best_n установить best_start = i и best_n = j - i.

5. Увеличить i = i + 1 и если i, j < length(A) go вернется к 2.

Общая сложность определяется начальной сложностью сортировки O (n log n). После сортировки заметьте, что сложность должна быть линейной, поскольку j < n может только увеличиваться, и мы делаем постоянное количество вещей на каждом шаге.

Answer 2

Сначала вы должны отсортировать массив (O (N) * log (N)), а затем пройти по массиву с начала, сохраняя интервал. если текущее число превышает интервал, сохраните этот массив. вы можете обновить хранилище, если найдете большее подмножество.

Временная сложность этого алгоритма будет O (N) * log (N) + O (N), примерно 2 * O (N). Сложность пространства будет O (N).