Алгоритм выравнивания массивов

Question

Дано 2 массива double одинаковой длины («Главный» массив «A» и вторичный массив «B»). Я хочу написать функцию, которая «выравнивает» B по A.

Я определил выравнивание таким образом, что для каждого элемента A, если B содержит этот элемент, тогда элемент должен быть помещен в тот же индекс, что и A.

Некоторая специфичность для A и B:

• A и B оба изначально отсортированы. После совмещения B НЕ нужно сортировать.
• A и B имеют одинаковую длину.
• Нет дубликатов ни в A, ни в B
• A и B довольно маленькие (максимум 10 элементов, чаще около 3-5 элементов).
• A не должно меняться.
• Я пометил вопрос C#, потому что это будет моя последняя реализация, но я могу адаптировать ответы
• Функция будет вызываться часто (100k / 1M в секунду), в идеале мне нужно что-то эффективное.

Ex1:
A = [10, 11, 12, 13]
B = [10, 12, 14 , 16] (начальный)
=> [10, 16, 12, 14] B Final ([10, 14, 12, 16] также допустимо, только размещение элементов «10» и «12» релевантно (другие элементы отсутствуют в A))

Ex2:
A = [10, 11, 12, 13]
B = [08, 09, 10, 11] (начальный)
=> [10, 11, 08, 09] B Final

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

Кто-нибудь знает существующий алгоритм для этого или чистый и эффективный способ сделать это?

Answer 1

Вот один способ. Не оптимально, но код неплох.

private static double[] align(double[] A, double[] B)
{
    var extras = B.Where(b => !A.Contains(b)).ToArray();
    int i = 0;
    var result = A.Select(a => B.Contains(a) ? a : extras[i++]).ToArray();
    return result;
}