반응형
정렬된 두 어레이를 정렬된 어레이로 병합하려면 어떻게 해야 합니까?
이것은 인터뷰에서 저에게 물어본 것입니다.그리고 제가 제공한 솔루션은 다음과 같습니다.
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a[i] < b[j])
{
answer[k] = a[i];
i++;
}
else
{
answer[k] = b[j];
j++;
}
k++;
}
while (i < a.length)
{
answer[k] = a[i];
i++;
k++;
}
while (j < b.length)
{
answer[k] = b[j];
j++;
k++;
}
return answer;
}
좀 더 효율적인 방법이 없을까요?
편집: 길이 메서드가 수정되었습니다.
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
while (i < a.length)
answer[k++] = a[i++];
while (j < b.length)
answer[k++] = b[j++];
return answer;
}
조금 더 콤팩트하지만 똑같아!
이렇게 훨씬 더 쿨하고 효율적이며 콤팩트한 구현에 대해 아무도 언급하지 않은 것이 놀랍습니다.
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = a.length - 1, j = b.length - 1, k = answer.length;
while (k > 0)
answer[--k] =
(j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
return answer;
}
관심장소
- 다른 O(n) 알고리즘과 같거나 적은 수의 연산을 하지만 말 그대로 단일 while loop에서 단일 스테이트먼트 내에서 수행합니다.
- 두 배열의 크기가 거의 같으면 O(n)에 대한 상수는 동일합니다.이 정말로 , 레레 with with with , with with with with with with with, 레 however with with with with with with with with,
System.arraycopy내부적으로는 단일 x86 어셈블리 명령으로 이 작업을 수행할 수 있기 때문에 이길 수 있습니다. - ★★
a[i] >= b[j]a[i] > b[j]이것에 의해, a와 b의 요소가 같을 때에, b보다 전의 a로부터의 요소를 요구하는 것으로 정의되는 「안정성」이 보증됩니다.
에는 '''를 할 수 있습니다.System.arraycopy다른 입력 배열의 끝에 도달했을 때 두 입력 배열의 꼬리를 복사합니다. 해서 것은O(n)하다, 하다, 솔솔솔 솔솔솔솔다다다다
개선할 수 있는 것은 마이크로 최적화이며, 전체적인 알고리즘은 정확합니다.
이 솔루션도 시스템을 사용하고 있다는 점을 제외하고는 다른 투고와 매우 유사합니다.arrayCopy를 클릭하여 나머지 어레이 요소를 복사합니다.
private static int[] sortedArrayMerge(int a[], int b[]) {
int result[] = new int[a.length +b.length];
int i =0; int j = 0;int k = 0;
while(i<a.length && j <b.length) {
if(a[i]<b[j]) {
result[k++] = a[i];
i++;
} else {
result[k++] = b[j];
j++;
}
}
System.arraycopy(a, i, result, k, (a.length -i));
System.arraycopy(b, j, result, k, (b.length -j));
return result;
}
업데이트된 기능을 소개합니다.중복을 제거합니다.누군가 이 기능을 사용할 수 있기를 바랍니다.
public static long[] merge2SortedAndRemoveDublicates(long[] a, long[] b) {
long[] answer = new long[a.length + b.length];
int i = 0, j = 0, k = 0;
long tmp;
while (i < a.length && j < b.length) {
tmp = a[i] < b[j] ? a[i++] : b[j++];
for ( ; i < a.length && a[i] == tmp; i++);
for ( ; j < b.length && b[j] == tmp; j++);
answer[k++] = tmp;
}
while (i < a.length) {
tmp = a[i++];
for ( ; i < a.length && a[i] == tmp; i++);
answer[k++] = tmp;
}
while (j < b.length) {
tmp = b[j++];
for ( ; j < b.length && b[j] == tmp; j++);
answer[k++] = tmp;
}
return Arrays.copyOf(answer, k);
}
아래와 같이 4개의 문장으로 할 수 있습니다.
int a[] = {10, 20, 30};
int b[]= {9, 14, 11};
int res[]=new int[a.legth+b.length];
System.arraycopy(a,0, res, 0, a.length);
System.arraycopy(b,0,res,a.length, b.length);
Array.sort(res)
Gallop Search 머지: O(n)가 아닌 O(log(n)*log(i))
저는 회색 수염 제안을 댓글로 구현했습니다.가장 큰 이유는 이 코드의 매우 효율적인 버전이 필요했기 때문입니다.
- 코드는 O(log(i)인 gallop Search를 사용합니다.여기서 i는 관련 인덱스가 존재하는 현재 인덱스로부터의 거리입니다.
- gallop 검색에서 적절한 범위를 식별한 후 코드에서는 binarySearch가 사용됩니다.gallop은 이 범위를 더 작은 범위로 제한하므로 결과 binarySearch도 O(log(i)가 됩니다.
- 갤럽과 머지는 뒤로 실행됩니다.이것은 미션 크리티컬하다고는 생각되지 않지만 어레이를 적절히 통합할 수 있습니다.어레이 중 하나에 결과 값을 저장하기에 충분한 공간이 있는 경우 단순히 병합 배열 및 결과 배열로 사용할 수 있습니다.이 경우 어레이 내에서 유효한 범위를 지정해야 합니다.
- 이 경우 메모리 할당이 필요하지 않습니다(중요한 작업에서 큰 절약).처리되지 않은 값은 덮어쓸 수 없으며 덮어쓸 수도 없습니다(역방향으로만 가능).실제로 입력과 결과 모두에 동일한 배열을 사용합니다.그것은 나쁜 영향을 받지 않을 것이다.
- Integer.compare()를 계속 사용했기 때문에 다른 목적으로 전환할 수 있었습니다.
- 이전에 증명된 정보를 사용하지 않고 약간 실수를 했을 가능성이 있습니다.예를 들어, 하나의 값이 이미 체크된 두 값의 범위에 대한 이진 검색 등입니다.또한 메인 루프를 설명하는 더 좋은 방법이 있을 수 있습니다.이러한 루프를 순서대로 2개의 연산으로 조합하면 플립 c 값이 필요하지 않습니다.매번 하나씩 할 거 아니까.광택제를 넣을 공간이 있다.
이것은 O(n)가 아닌 O(log(n)*log(i)의 시간이 복잡하기 때문에 가장 효율적인 방법입니다.그리고 최악의 경우 O(n)의 시간 복잡도입니다.어레이가 뭉쳐져 있고 가치의 문자열이 긴 경우, 다른 방법으로는 부족하지만, 그렇지 않으면 어레이보다 나을 뿐입니다.
병합 배열의 끝에 두 개의 읽기 값과 결과 배열 내의 쓰기 값이 있습니다.어떤 끝값이 더 작은지 알아내면 해당 배열(1, 2, 4, 8, 16, 32 등)에 대해 gallp 검색을 수행합니다.다른 배열의 읽기 값이 더 큰 범위를 찾은 경우.이 값은 해당 범위를 이진법으로 검색합니다(범위를 반으로 자르고 올바른 절반을 검색한 후 단일 값이 될 때까지 반복).그런 다음 어레이는 이러한 값을 쓰기 위치에 복사합니다.복사는 반드시 어느 하나의 읽기 배열에서나 같은 값을 덮어쓸 수 없도록 이동됩니다(즉, 쓰기 배열과 읽기 배열은 같을 수 있습니다).그런 다음 현재 다른 어레이의 새 읽기 값보다 작은 것으로 알려진 다른 어레이에 대해 동일한 작업을 수행합니다.
static public int gallopSearch(int current, int[] array, int v) {
int d = 1;
int seek = current - d;
int prevIteration = seek;
while (seek > 0) {
if (Integer.compare(array[seek], v) <= 0) {
break;
}
prevIteration = seek;
d <<= 1;
seek = current - d;
if (seek < 0) {
seek = 0;
}
}
if (prevIteration != seek) {
seek = binarySearch(array, seek, prevIteration, v);
seek = seek >= 0 ? seek : ~seek;
}
return seek;
}
static public int binarySearch(int[] list, int fromIndex, int toIndex, int v) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = list[mid];
int cmp = Integer.compare(midVal, v);
if (cmp < 0) {
low = mid + 1;
} else if (cmp > 0) {
high = mid - 1;
} else {
return mid;// key found
}
}
return -(low + 1);// key not found.
}
static public int[] sortedArrayMerge(int[] a, int[] b) {
return sortedArrayMerge(null, a, a.length, b, b.length);
}
static public int[] sortedArrayMerge(int[] results, int[] a, int aRead, int b[], int bRead) {
int write = aRead + bRead, length, gallopPos;
if ((results == null) || (results.length < write)) {
results = new int[write];
}
if (aRead > 0 && bRead > 0) {
int c = Integer.compare(a[aRead - 1], b[bRead - 1]);
while (aRead > 0 && bRead > 0) {
switch (c) {
default:
gallopPos = gallopSearch(aRead, a, b[bRead-1]);
length = (aRead - gallopPos);
write -= length;
aRead = gallopPos;
System.arraycopy(a, gallopPos--, results, write, length);
c = -1;
break;
case -1:
gallopPos = gallopSearch(bRead, b, a[aRead-1]);
length = (bRead - gallopPos);
write -= length;
bRead = gallopPos;
System.arraycopy(b, gallopPos--, results, write, length);
c = 1;
break;
}
}
}
if (bRead > 0) {
if (b != results) {
System.arraycopy(b, 0, results, 0, bRead);
}
} else if (aRead > 0) {
if (a != results) {
System.arraycopy(a, 0, results, 0, aRead);
}
}
return results;
}
이것이 가장 효율적인 방법일 것입니다.
일부 응답에는 중복 제거 기능이 있습니다.각 항목을 실제로 비교해야 하므로 O(n) 알고리즘이 필요합니다.그 후에 적용할 독립 실행형 프로그램이 있습니다.여러 엔트리를 모두 확인해야 할 경우 전체 엔트리를 빠르게 검색할 수 없습니다.복제 항목이 많으면 빠르게 검색할 수도 있습니다.
static public int removeDuplicates(int[] list, int size) {
int write = 1;
for (int read = 1; read < size; read++) {
if (list[read] == list[read - 1]) {
continue;
}
list[write++] = list[read];
}
return write;
}
업데이트: 이전 답변입니다. 끔찍한 코드는 아니지만 위의 답변보다 확실히 열등합니다.
또 다른 불필요한 최적화입니다.이 명령어는 엔드 비트에 대해 어레이 복사를 호출할 뿐만 아니라 선두 비트도 호출합니다.O(log(n)에서 오버랩되지 않는 입문 데이터를 바이너리서치로 처리합니다.O(log(n) + n)는 O(n)이며, 특히 Marge 어레이 간에 오버랩이 전혀 없는 경우 등 경우에 따라서는 효과가 현저하게 나타날 수 있습니다.
private static int binarySearch(int[] array, int low, int high, int v) {
high = high - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = array[mid];
if (midVal > v)
low = mid + 1;
else if (midVal < v)
high = mid - 1;
else
return mid; // key found
}
return low;//traditionally, -(low + 1); // key not found.
}
private static int[] sortedArrayMerge(int a[], int b[]) {
int result[] = new int[a.length + b.length];
int k, i = 0, j = 0;
if (a[0] > b[0]) {
k = i = binarySearch(b, 0, b.length, a[0]);
System.arraycopy(b, 0, result, 0, i);
} else {
k = j = binarySearch(a, 0, a.length, b[0]);
System.arraycopy(a, 0, result, 0, j);
}
while (i < a.length && j < b.length) {
result[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
}
if (j < b.length) {
System.arraycopy(b, j, result, k, (b.length - j));
} else {
System.arraycopy(a, i, result, k, (a.length - i));
}
return result;
}
javascript로 작성해야 했습니다.여기 있습니다.
function merge(a, b) {
var result = [];
var ai = 0;
var bi = 0;
while (true) {
if ( ai < a.length && bi < b.length) {
if (a[ai] < b[bi]) {
result.push(a[ai]);
ai++;
} else if (a[ai] > b[bi]) {
result.push(b[bi]);
bi++;
} else {
result.push(a[ai]);
result.push(b[bi]);
ai++;
bi++;
}
} else if (ai < a.length) {
result.push.apply(result, a.slice(ai, a.length));
break;
} else if (bi < b.length) {
result.push.apply(result, b.slice(bi, b.length));
break;
} else {
break;
}
}
return result;
}
Apache 컬렉션은 버전 4 이후부터 조합 방법을 지원합니다.이 작업을 수행하려면collate메서드:
org.apache.commons.collections4.CollectionUtils
javadoc에서 인용:
collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)정렬된 두 컬렉션을 병합합니다.
a그리고.b비교기 c에 따른 요소의 순서가 유지되도록 정렬된 단일 목록으로 나뉩니다.
바퀴를 다시 발명하지 마세요!문서 참조: http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html
다음은 javascript로 작성된 단축형식입니다.
function sort( a1, a2 ) {
var i = 0
, j = 0
, l1 = a1.length
, l2 = a2.length
, a = [];
while( i < l1 && j < l2 ) {
a1[i] < a2[j] ? (a.push(a1[i]), i++) : (a.push( a2[j]), j++);
}
i < l1 && ( a = a.concat( a1.splice(i) ));
j < l2 && ( a = a.concat( a2.splice(j) ));
return a;
}
public class Merge {
// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi);
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
// postcondition: a[lo .. hi] is sorted
assert isSorted(a, lo, hi);
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
}
/***********************************************************************
* Helper sorting functions
***********************************************************************/
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/***********************************************************************
* Check if array is sorted - useful for debugging
***********************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
/***********************************************************************
* Index mergesort
***********************************************************************/
// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = index[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) index[k] = aux[j++];
else if (j > hi) index[k] = aux[i++];
else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
else index[k] = aux[i++];
}
}
// return a permutation that gives the elements in a[] in ascending order
// do not change the original array a[]
public static int[] indexSort(Comparable[] a) {
int N = a.length;
int[] index = new int[N];
for (int i = 0; i < N; i++)
index[i] = i;
int[] aux = new int[N];
sort(a, index, aux, 0, N-1);
return index;
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, index, aux, lo, mid);
sort(a, index, aux, mid + 1, hi);
merge(a, index, aux, lo, mid, hi);
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
// Read strings from standard input, sort them, and print.
public static void main(String[] args) {
String[] a = StdIn.readStrings();
Merge.sort(a);
show(a);
}
}
더 큰 정렬 어레이에 스킵 리스트를 도입함으로써 비교 횟수를 줄이고 세 번째 어레이에 복사하는 프로세스를 고속화할 수 있다고 생각합니다.어레이가 너무 크면 좋을 수 있습니다.
public int[] merge(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int aIndex, bIndex = 0;
for (int i = 0; i < result.length; i++) {
if (aIndex < a.length && bIndex < b.length) {
if (a[aIndex] < b[bIndex]) {
result[i] = a[aIndex];
aIndex++;
} else {
result[i] = b[bIndex];
bIndex++;
}
} else if (aIndex < a.length) {
result[i] = a[aIndex];
aIndex++;
} else {
result[i] = b[bIndex];
bIndex++;
}
}
return result;
}
public static int[] merge(int[] a, int[] b) {
int[] mergedArray = new int[(a.length + b.length)];
int i = 0, j = 0;
int mergedArrayIndex = 0;
for (; i < a.length || j < b.length;) {
if (i < a.length && j < b.length) {
if (a[i] < b[j]) {
mergedArray[mergedArrayIndex] = a[i];
i++;
} else {
mergedArray[mergedArrayIndex] = b[j];
j++;
}
} else if (i < a.length) {
mergedArray[mergedArrayIndex] = a[i];
i++;
} else if (j < b.length) {
mergedArray[mergedArrayIndex] = b[j];
j++;
}
mergedArrayIndex++;
}
return mergedArray;
}
알고리즘은 여러 가지 방법으로 강화될 수 있습니다.예를 들어, 다음과 같은 경우 체크하는 것이 합리적입니다.a[m-1]<b[0]또는b[n-1]<a[0]어떤 경우에도 더 이상 비교할 필요가 없습니다.알고리즘은 소스 어레이를 결과 어레이의 올바른 순서로 복사할 수 있습니다.
더 복잡한 확장 기능으로는 인터리빙 부품 검색과 이들 부품에 대한 병합 알고리즘만 실행할 수 있습니다.병합된 어레이의 크기가 수십 번 다를 경우 시간을 크게 절약할 수 있습니다.
이 문제는 2개의 정렬된 서브어레이가1개의 정렬된 서브어레이로 결합되는 머지소트 알고리즘과 관련되어 있습니다.CLRS 책자는 알고리즘의 예를 제시하며, 각 어레이의 끝에 sentinel 값(다른 값보다 더 큰 값)을 추가하여 끝에 도달했는지 확인할 필요가 없습니다.
Python으로 썼는데 Java로도 잘 번역될 거예요.
def func(a, b):
class sentinel(object):
def __lt__(*_):
return False
ax, bx, c = a[:] + [sentinel()], b[:] + [sentinel()], []
i, j = 0, 0
for k in range(len(a) + len(b)):
if ax[i] < bx[j]:
c.append(ax[i])
i += 1
else:
c.append(bx[j])
j += 1
return c
2개의 스레드를 사용하여 어레이를 전면에서1개, 후면에서1개를 채울 수 있습니다.
예를 들어 각 스레드가 값의 절반을 삽입하는 경우 등 숫자의 경우 동기화 없이 작동할 수 있습니다.
//How to merge two sorted arrays into a sorted array without duplicates?
//simple C Coding
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
main()
{
int InputArray1[] ={1,4,5,7,8,9,12,13,14,17,40};
int InputArray2[] ={4,5,11,14,15,17,18,19,112,122,122,122,122};
int n=10;
int OutputArray[30];
int i=0,j=0,k=0;
//k=OutputArray
while(i<11 && j<13)
{
if(InputArray1[i]<InputArray2[j])
{
if (k == 0 || InputArray1[i]!= OutputArray[k-1])
{
OutputArray[k++] = InputArray1[i];
}
i=i+1;
}
else if(InputArray1[i]>InputArray2[j])
{
if (k == 0 || InputArray2[j]!= OutputArray[k-1])
{
OutputArray[k++] = InputArray2[j];
}
j=j+1;
}
else
{
if (k == 0 || InputArray1[i]!= OutputArray[k-1])
{
OutputArray[k++] = InputArray1[i];
}
i=i+1;
j=j+1;
}
};
while(i<11)
{
if(InputArray1[i]!= OutputArray[k-1])
OutputArray[k++] = InputArray1[i++];
else
i++;
}
while(j<13)
{
if(InputArray2[j]!= OutputArray[k-1])
OutputArray[k++] = InputArray2[j++];
else
j++;
}
for(i=0; i<k; i++)
{
printf("sorted data:%d\n",OutputArray[i]);
};
}
public static int[] merge(int[] listA, int[] listB) {
int[] mergedList = new int[ listA.length + listB.length];
int i = 0; // Counter for listA
int j = 0; // Counter for listB
int k = 0; // Counter for mergedList
while (true) {
if (i >= listA.length && j >= listB.length) {
break;
}
if (i < listA.length && j < listB.length) { // If both counters are valid.
if (listA[i] <= listB[j]) {
mergedList[k] = listA[i];
k++;
i++;
} else {
mergedList[k] = listB[j];
k++;
j++;
}
} else if (i < listA.length && j >= listB.length) { // If only A's counter is valid.
mergedList[k] = listA[i];
k++;
i++;
} else if (i <= listA.length && j < listB.length) { // If only B's counter is valid
mergedList[k] = listB[j];
k++;
j++;
}
}
return mergedList;
}
var arrCombo = function(arr1, arr2){
return arr1.concat(arr2).sort(function(x, y) {
return x - y;
});
};
내가 가장 좋아하는 프로그래밍 언어는 자바스크립트이다.
function mergeSortedArrays(a, b){
var result = [];
var sI = 0;
var lI = 0;
var smallArr;
var largeArr;
var temp;
if(typeof b[0] === 'undefined' || a[0]<b[0]){
smallArr = a;
largeArr = b;
} else{
smallArr = b;
largeArr = a;
}
while(typeof smallArr[sI] !== 'undefined'){
result.push(smallArr[sI]);
sI++;
if(smallArr[sI]>largeArr[lI] || typeof smallArr[sI] === 'undefined'){
temp = smallArr;
smallArr = largeArr;
largeArr = temp;
temp = sI;
sI = lI;
lI = temp;
}
}
return result;
}
시스템을 사용할 수 있습니다.어레이 복사
public static byte[] merge(byte[] first, byte[] second){
int len = first.length + second.length;
byte[] full = new byte[len];
System.arraycopy(first, 0, full, 0, first.length);
System.arraycopy(second, 0, full, first.length, second.length);
return full;
}
public static void main(String[] args) {
int[] arr1 = {2,4,6,8,10,999};
int[] arr2 = {1,3,5,9,100,1001};
int[] arr3 = new int[arr1.length + arr2.length];
int temp = 0;
for (int i = 0; i < (arr3.length); i++) {
if(temp == arr2.length){
arr3[i] = arr1[i-temp];
}
else if (((i-temp)<(arr1.length)) && (arr1[i-temp] < arr2[temp])){
arr3[i] = arr1[i-temp];
}
else{
arr3[i] = arr2[temp];
temp++;
}
}
for (int i : arr3) {
System.out.print(i + ", ");
}
}
출력은 다음과 같습니다.
1, 2, 3, 4, 5, 6, 8, 9, 10, 100, 999, 1001,
3진 연산자를 사용하여 코드를 좀 더 컴팩트하게 만들 수 있습니다.
public static int[] mergeArrays(int[] a1, int[] a2) {
int[] res = new int[a1.length + a2.length];
int i = 0, j = 0;
while (i < a1.length && j < a2.length) {
res[i + j] = a1[i] < a2[j] ? a1[i++] : a2[j++];
}
while (i < a1.length) {
res[i + j] = a1[i++];
}
while (j < a2.length) {
res[i + j] = a2[j++];
}
return res;
}
public static int[] mergeSorted(int[] left, int[] right) {
System.out.println("merging " + Arrays.toString(left) + " and " + Arrays.toString(right));
int[] merged = new int[left.length + right.length];
int nextIndexLeft = 0;
int nextIndexRight = 0;
for (int i = 0; i < merged.length; i++) {
if (nextIndexLeft >= left.length) {
System.arraycopy(right, nextIndexRight, merged, i, right.length - nextIndexRight);
break;
}
if (nextIndexRight >= right.length) {
System.arraycopy(left, nextIndexLeft, merged, i, left.length - nextIndexLeft);
break;
}
if (left[nextIndexLeft] <= right[nextIndexRight]) {
merged[i] = left[nextIndexLeft];
nextIndexLeft++;
continue;
}
if (left[nextIndexLeft] > right[nextIndexRight]) {
merged[i] = right[nextIndexRight];
nextIndexRight++;
continue;
}
}
System.out.println("merged : " + Arrays.toString(merged));
return merged;
}
기존 솔루션과 조금 다른 점만
O(m+n) 시간 복잡도로 정렬된 2개의 어레이를 Marge하려면 1개의 루프만으로 다음 방법을 사용합니다.m과 n은 첫 번째 어레이와 두 번째 어레이의 길이입니다.
public class MargeSortedArray {
public static void main(String[] args) {
int[] array = new int[]{1,3,4,7};
int[] array2 = new int[]{2,5,6,8,12,45};
int[] newarry = margeToSortedArray(array, array2);
//newarray is marged array
}
// marge two sorted array with o(a+n) time complexity
public static int[] margeToSortedArray(int[] array, int[] array2) {
int newarrlen = array.length+array2.length;
int[] newarr = new int[newarrlen];
int pos1=0,pos2=0;
int len1=array.length, len2=array2.length;
for(int i =0;i<newarrlen;i++) {
if(pos1>=len1) {
newarr[i]=array2[pos2];
pos2++;
continue;
}
if(pos2>=len2) {
newarr[i]=array[pos1];
pos1++;
continue;
}
if(array[pos1]>array2[pos2]) {
newarr[i]=array2[pos2];
pos2++;
} else {
newarr[i]=array[pos1];
pos1++;
}
}
return newarr;
}
}
var arr1 = [2,10,20,30,100];
var arr2 = [2,4,5,6,7,8,9];
var j = 0;
var i =0;
var newArray = [];
for(var x=0;x< (arr1.length + arr2.length);x++){
if(arr1[i] >= arr2[j]){ //check if element arr2 is equal and less than arr1 element
newArray.push(arr2[j]);
j++;
}else if(arr1[i] < arr2[j]){ //check if element arr1 index value is less than arr2 element
newArray.push(arr1[i]);
i++;
}
else if(i == arr1.length || j < arr2.length){ // add remaining arr2 element
newArray.push(arr2[j]);
j++
}else{ // add remaining arr1 element
newArray.push(arr1[i]);
i++
}
}
console.log(newArray);
그 질문은 특정한 언어를 가정하지 않기 때문에.다음은 Python의 솔루션입니다.어레이가 이미 정렬되어 있다고 가정합니다.
접근법 1 - numpy 어레이 사용: numpy Import
arr1 = numpy.asarray([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 15, 55])
arr2 = numpy.asarray([11, 32, 43, 45, 66, 76, 88])
array = numpy.concatenate((arr1,arr2), axis=0)
array.sort()
접근법 2 - 목록을 사용하여 목록을 정렬했다고 가정합니다.
list_new = list1.extend(list2)
list_new.sort()
중복을 삭제하는 Java 구현은 다음과 같습니다.
public static int[] mergesort(int[] a, int[] b) {
int[] c = new int[a.length + b.length];
int i = 0, j = 0, k = 0, duplicateCount = 0;
while (i < a.length || j < b.length) {
if (i < a.length && j < b.length) {
if (a[i] == b[j]) {
c[k] = a[i];
i++;j++;duplicateCount++;
} else {
c[k] = a[i] < b[j] ? a[i++] : b[j++];
}
} else if (i < a.length) {
c[k] = a[i++];
} else if (j < a.length) {
c[k] = b[j++];
}
k++;
}
return Arrays.copyOf(c, c.length - duplicateCount);
}
언급URL : https://stackoverflow.com/questions/5958169/how-to-merge-two-sorted-arrays-into-a-sorted-array
반응형
'programing' 카테고리의 다른 글
| C/C++에 표준 기호 함수(signum, sgn)가 있습니까? (0) | 2022.08.25 |
|---|---|
| Vuex: _이것.$store가 정의되지 않았습니다. (0) | 2022.08.25 |
| 만약 내가 스위치 경우 기본을 쓰는 게 어떨까? (0) | 2022.08.25 |
| Vue js. 재귀 구성 요소가 내 인생을 망친다. (0) | 2022.08.25 |
| router.push(location, onComplete?, onAbort 등)를 사용한 onComplete 및 onAbort 콜백이 있습니까? (0) | 2022.08.25 |