Количество элементов, которые удовлетворяют соотношению

Question

Учитывая два массива:

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

сосчитать число элементов x, y, которые удовлетворяют условию, что x находится перед y в обоих массивах.

---

Прогресс до сих пор:

Отсортировать массивы по их индексам. Например, это будет:

     object: 1 2 3 4 5 6 7 
indexes in the first array: 6 0 4 3 1 2 5 
indexes in the secnod array: 1 3 4 6 0 2 5 

и сравнить каждый кортеж с другим. Если кортеж a имеет либо оба индекса ниже или выше, чем кортеж b, увеличивайте количество элементов, удовлетворяющих условию.

Это временная сложность (N^2)/2, поэтому O (N^2), которая слишком медленная. Я понимаю, что не может быть лучшего худшего сценария сложности, но меня больше всего интересует средний результат. Итак: есть ли лучший способ/алгоритм?

Я думал об использовании переходных свойств (если оба (x,y) и (y,z) удовлетворяют условию, то (x,z) удовлетворяет его также), но не повезло.

---

Тестовые

Для массивов:

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

Пары, которые удовлетворяют условию являются:

(5,1) (2,3) (2,4) (2,7) (5,3) (6,3) (3,7) (5,4) (6,4) (5,6) (5,7) (6,7) 

Для массивов:

1 2 3 4 5 6 7 
1 2 3 4 5 6 7 

Пары, которые удовлетворяют условию являются:

(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,3) (2,4) (2,5) (2,6) (2,7) (3,4) (3,5) (3,6) (3,7) (4,5) (4,6) (4,7) (5,6) (5,7) (6,7) 

Answer 1

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

The Beach Boys Принцип

термин, используемый мой учитель Исчисление и на самом деле очень применимо решение проблемы техники. В принципе, если у вас есть жесткая проблема, скажите «было бы неплохо, если бы ...», и посмотреть, есть ли что-то, что облегчит ситуацию. Если есть, посмотрите, можете ли вы это сделать.

В этом случае было бы неплохо, если бы был заказан верхний массив и только [1, 2, 3 ...]? Это позволило бы решить эту проблему намного проще, так как она превращает проблему с двумя массивами в проблему с одним массивом.

Ну, это может быть так! Вы можете сопоставить любую из этих проблем с тем, что имеет упорядоченный первый массив.

Первый пример, который вы перечислили:

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

Я считаю, что проблема выше эквивалентна следующей задаче:

1 2 3 4 5 6 7 
2 7 3 1 5 6 4 

Сопоставления

Я просто сделать простой зашифрованное замещение 2-> 1 5-> 2 6-> 3 4-> 4 3-> 5 7-> 6 1-> 7 (Почему это конкретное отображение?). Это оставляет основную структуру проблемы одинаковой. Затем вы можете решить эту проблему, а затем отменить отображение.

Вы обнаружите, что эта техника сопоставления одной проблемы с более простой проблемой часто возникает в информатике, особенно в ваших алгоритмах и классах вычислимости.

Теперь у вас есть один массив проблемы, чтобы найти все пары:

2 7 3 1 5 6 4 

Временная сложность этого я оставляю упражнение для читателя.

P.S. Не забывайте о временной сложности отмены вашего картографирования. Иногда вы решите проблему, думая, что будет легко узнать, что построение и деконструирование вашего картографирования чрезвычайно дорого, и вам нужно вернуться к чертежной доске.