Сортировка массива на основе сравнения с другим массивом тех же элементов в другом порядке

Question

С учетом двух массивов

a[] = {1,3,2,4} 
b[] = {4,2,3,1} 

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

Answer 1

Я могу дать вам алгоритм O (N * log (N)) сложность времени на основе быстрой сортировки.

1. Произвольно выбрать элемент a1 в массиве A
2. Используйте a1 для разбиения массива B, обратите внимание, что вам нужно только сравнить каждый элемент в массиве B с a1
3. Секционирование возвращает позицию b1.Используйте b1 для разбиения массива A (аналогично шагу 2)
4. Переходите к шагу 1 для секционированных подмассивов, если их длина больше 1.

Сложность времени: T (N) = 2 * T (N / 2) + O (N) .Таким образом, общая сложность составляет O (N * log (N)) согласно основной теореме.

Answer 2

Не уверен, что я правильно понял вопрос, но, насколько я понимаю, задача состоит в следующем:

Сортировать заданный массив a без , сравнивая любые два элемента из a напрямую.Однако нам дается второй массив b, который гарантированно содержит те же элементы, что и a, но в произвольном порядке.Вам не разрешено изменять b (иначе просто сортируйте b и возвращайте его ...).

В случае, если элементы в a различны, это легко: для каждого элементав a посчитайте, сколько элементов в b меньше.Это число дает нам индекс (на основе нуля) в отсортированном порядке.

Случай, когда элементы не обязательно различны, оставлен читателю:)

Answer 3

Я не уверен, что это обман, но почему бы не сохранить индексы b в a.Затем сортируйте с помощью быстрой сортировки, но сравните b [a [x]] b [a [y]].Тогда вы не сравниваете какие-либо два элемента напрямую.Когда закончите, просто замените значения индекса в a фактическими значениями от b, на которые они указывают.

(редактировать после того, как OP был отредактирован)

Если бы я видел вопрос таким, какой он есть сейчасмой ответ «не тот ответ, который они действительно искали» был бы следующим: переупорядочить b, чтобы соответствовать a, скопировав a в b (они имеют идентичное содержимое).Сортируйте, используя быстрый алгоритм по вашему выбору, но при сравнении сравните a [x] с b [y].Сделайте одинаковые перестановки для обоих массивов.Вы сортируете оба без сравнения элементов из одного массива.