Попытка найти эффективный алгоритм, который находит разницу между двумя отсортированными массивами, в то время как один из массивов всегда является подмножеством другого.Рассчитать разницу между двумя отсортированными массивами
Например, мы можем иметь две отсортированные массивы
- [1, 2, 3, 4]
- [1, 3, 4]
И второй массив является подмножество первого.
Потенциального решение: Наиболее эффективный алгоритма я могу думать о том, чтобы перебирать массивы одновременно и сравнить элемент, так как они сортируются. Другая оптимизация - создать счетчик разницы в длине между двумя массивами, и если мы столкнулись с числом разных элементов, равным разности, которую мы вычисляли спереди, алгоритм может остановиться в этой точке.
Возможно, это самый эффективный алгоритм, но я хотел бы услышать мнения ваших ребят.
Линейное время - лучшее, что вы можете надеяться на асимптотически. Похоже, ваш первый подход звучит. Я не понимаю второго. –
Первый подход прост; второй наиболее эффективен, так как он сочетает первый. В любом случае это все линейное время. Поскольку вы, вероятно, потратили больше времени на сортировку, не беспокойтесь об этом шаге :) – dan
Второй подход будет таким же плохим, как и первый, поскольку поиск размера двух массивов по сути означает, что вы (или библиотечная функция) подсчитали элементы линейно. – user1952500