Найдите одинаковые числа между интервалами [a,b]
Предположим, у меня есть 3 массива последовательных чисел
a = [1, 2, 3]
b = [2, 3, 4]
c = [3, 4]
Тогда одно и то же число, которое появляется во всех трех массивах, равно 3.
Мой алгоритм состоит в том, чтобы использовать два цикла for друг в друге, чтобы проверить один и тот же массив и поместить его в другой массив (назовем его d). потом
d = [2, 3] (d = a overlap b)
И используйте его снова для проверки массива d и c => Окончательный результат равен 1, потому что во всех трех массивах появляется только 1 число.
e = [3] (e = c overlap d) => e.length = 1
Кроме этого, если существует только 1 массив, алгоритм должен вернуть длину массива, так как все его числа появляются сами по себе. Но я думаю, что мой упомянутый выше алгоритм займет слишком много времени, потому что числа в массиве могут достигать 10 ^ 5. Итак, есть идеи о лучшем алгоритме?
Вы можете вычислить максимум первого элемента массивов и минимум последних элементов массива. Это диапазон чисел во всех списках.
Ответы 1
But I think my said algo above would take too long because the numbers of array can go up to 105. So, any idea of a better algorithm?
Да, поскольку это диапазоны, вы в основном хотите вычислить пересечение диапазонов. Это означает, что вы можете рассчитать максимальное значение
Вам не нужно вычислять перекрытие, перебирая первый список, и проверять, являются ли они членами последнего списка. Поскольку это последовательные числа, мы можем легко узнать, что такое перекрытие.
Короче говоря, перекрытие [а, ..., б] и [компакт диск] равно [ max(а,с), ..., min(б,г) ], нет необходимости проверять промежуточные элементы.
2не появляется вc?