Эффективный способ нахождения последовательных чисел по нескольким массивам?

Question

Я не ищу ни кода, ни чего-либо для меня. Мне нужна помощь, чтобы начать работу в правильном направлении, но не знаю, как это сделать. Если бы кто-то мог предоставить некоторые ресурсы о том, как решить эти проблемы, я бы очень признателен. Я сидел со своей записной книжкой, и мне трудно разработать алгоритм, который может делать то, что я пытаюсь сделать.

я, вероятно, может сделать:

foreach element in array1 
    foreach element in array2 
     check if array1[i] == array2[j]+x 

Я считаю, что это будет работать как для прямой и обратной последовательностей, а также для кратных просто проверить array1[i] % array2[j] == 0. У меня есть список, который содержит int массивы, и я получаю list[index] (для array1) и list[index+1] для array2, но это решение может быть сложным и длительным быстро, особенно с большими массивами и большим списком этих массивов. Таким образом, я ищу лучшее решение.


Я пытаюсь найти алгоритм поиска последовательных чисел в разных массивах.

Например:

[1, 5, 7] и [9, 2, 11] обнаружил бы, что 1 и 2 являются последовательными.

Это также должно работать для нескольких последовательностей в нескольких массивах. Поэтому, если есть третий массив [24, 3, 15], он также будет содержать 3 в этой последовательности и продолжит переход к следующему массиву, пока не будет числа, которое соответствует last sequential element + 1.

Он также должен иметь возможность находить более одной последовательности между массивами.

Например:

[1, 5, 7] и [6, 3, 8] обнаружил бы, что 5 и 6 являются последовательными, а также 7 и 8 являются последовательными.

Я также заинтересован в поиске обратных последовательностей.

Например: [1, 5, 7] и [9, 4, 11] вернуться бы 5 и 4 являются обратной последовательности.

Пример со всеми:

[1, 5, 8, 11] и [2, 6, 7, 10] бы вернуть 1 и 2 являются последовательными, 5 и 6 являются последовательными, 8 и 7 являются обратными последовательными, 11 и 10 являются обратными последовательным.

Он также может перекрываться:

[1, 5, 7, 9] и [2, 6, 11, 13] вернется 1 и 2 последовательным, 5 и 6 последовательный, а также 7 и 6 обратной последовательности.

Я также хочу, чтобы расширить это, чтобы проверить номера с разницей x (выше примеры сверяться с разницей 1).

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

Пример: [5, 7, 9] и [10, 27, 8] вернется 5 и 10 кратными, 9 и 27 как кратные.

и номера с одинаковыми местами.

Пример: [3, 5, 7] и [13, 23, 25] вернуться бы 3 и 13 и 23 имеют те же самые, цифры.

Answer 1

Используйте словарь (набор или HashMap)

dictionary1 = {} 

Пройтись каждого элемента первого массива и добавить его в словарь. [1, 5, 7]

Теперь dictionary1 = {1:true, 5:true, 7:true}

dictionary2 = {} 

Теперь пройти через каждый пункт в [6, 3, 8] и поиска, если она является частью последовательности.

6 является частью последовательности, потому что dictionary1[6+1] == true так dictionary2[6] = true

Мы получаем dictionary2 = {6:true, 8:true}

Теперь набор dictionary1 = dictionary2 и dictionary2 = {}, и перейти на третий массив .. и так далее.

Мы отслеживаем только последовательности. Поскольку каждый поиск равен O (1), и мы выполняем 2 поиска по числу (например, 6-1 и 6 + 1), общее число n * O (1), которое равно O (N) (N - число числа во всех массивах).

Answer 2

Сила подход грубого указан в вашем псевдокоде будет O(c^n) (экспоненциальным), где c среднее количество элементов в массив, и n этого числа общих массивов.

Если входное пространство разреженным (это означает, что будет больше недостающие числа в среднем, чем представление чисел), то один из способов ускорить этот процесс является первым создать единый упорядоченный набор всех уникальных номеров из всех ваши разные массивы. Этот «мастер» набор позволит вам досрочно выйти (т. Е. break операторов в ваших циклах) на любые последовательности, которые не являются жизнеспособными.

Например, если у нас есть входные массивы [1, 5, 7] и [6, 3, 8] и [9, 11, 2], мастер упорядоченный набор будет {1, 2, 3, 5, 6, 7, 8, 9, 11}. Если мы ищем n+1 последовательностей типа, мы могли бы пропустить когда-либо продолжает проверять любую последовательность, которая содержит 3 или 9 или 11 (так как значение n+1 в нет на следующий индекс в отсортированном множестве. В то время ускорений не резкое в этом конкретном примере, если у вас есть сотни входных массивов и очень большой диапазон значений для n (разреженность), то ускорения должны быть экспоненциальными, потому что вы сможете быстро выйти на многие перестановки. Если входное пространство не является разреженным (например, в этом примере, где у нас не было много отверстий), ускорения будут меньше экспоненциального.

Дальнейшим усовершенствованием было бы сохранить «главный» набор пар ключ-значение, где ключ - это значение n, как показано в примере выше, а часть значения пары - это список индексов любых массивов, которые содержат это значение. Мастер-набор предыдущего примера будет тогда: {[1, 0], [2, 2], [3, 1], [5, 0], [6, 1], [7, 0], [8, 1], [9, 2], [11, 2]}. С этой архитектурой время сканирования может быть настолько низким, как O(c*n), потому что вы можете просто пройти этот единственный отсортированный мастер-набор, который ищет допустимые последовательности вместо циклического переключения по всем субмассивам.Кроме того, чтобы индексы массива увеличивались, вы можете четко видеть, что последовательность 1->2 может быть пропущена, потому что массивы находятся не в правильном порядке, и то же самое с последовательностью 2->3 и т. Д. Обратите внимание, что этот пример игрушки несколько упрощен, потому что на практике вам понадобится список индексов для частей значения пар ключ-значение. Это было бы необходимо, если бы одно значение n появилось в нескольких массивах (дублирующиеся значения).