Слияние двух массивов на месте
Согласно документации: ОТ (Transact-SQL) :
::=
[ { INNER | { { LEFT | RIGHT | FULL } [ OUTER ] } } [ ] ]
JOIN
ключевое слово OUTER отмечено как дополнительное (включенный в квадратные скобки). В этом конкретном случае, определяете ли Вы OUTER или не не имеете никакого значения. Обратите внимание, что, в то время как другие элементы пункта соединения также отмечен как дополнительный, уехав их , будет иметь значение.
, Например, вся часть типа JOIN пункт является дополнительным, в этом случае значение по умолчанию INNER, если Вы просто определяете JOIN. Другими словами, это законно:
SELECT *
FROM A JOIN B ON A.X = B.Y
Вот список эквивалентных синтаксисов:
A LEFT JOIN B A LEFT OUTER JOIN B
A RIGHT JOIN B A RIGHT OUTER JOIN B
A FULL JOIN B A FULL OUTER JOIN B
A INNER JOIN B A JOIN B
Также смотрят на ответ, я оставил на этом другой ТАК вопрос: SQL оставил соединение по сравнению с несколькими таблицами на ОТ строки? .
4 ответа
Выполняйте регулярную сортировку слиянием, но сначала сравнивайте самые большие числа в обратном порядке, сохраняя (переворачивая) конец первого массива, возвращаясь назад. Таким образом, элементы, которые вы объединяете, никогда не перезаписываются (это легко увидеть, если вы подумаете об этом на мгновение).
Переместите содержимое первого массива в конец первого массива так, чтобы пустые элементы теперь находились в начале. Затем объедините две последовательности, как обычно, в первый массив.
На месте в основном требуется, чтобы мы использовали только «постоянный» объем памяти, который не меняется при разных размерах входного массива. Однако сам вопрос выделяет дополнительный объем памяти, равный размеру одного из двух входных массивов, который в худшем случае равен O (n) памяти. Это в основном делает идею «на месте» бессмысленной ...
Вопрос может быть лучше сформулирован как «слияние без дополнительной памяти», что является более точным описанием его реального намерения ...
// merge the elements in B[] to A[], starting from the last one
void merge(int A[], int m, int B[], int n) {
// m-1 and n-1 represent the current element index in A[] and B[] respectively
while (n > 0) { // there are still elements in B[] not merged
if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[]
A[m+n-1] = A[m-1]; // move current element of A[] to its right position
--m; // decrease current element index of A[]
}
else { // current element in A[] <= current element in B[]
A[m+n-1] = B[n-1]; // move current element in B[] to its right position
--n; // decrease current element index of B[]
}
}
}