반응형
정렬 된 두 배열을 정렬 된 배열로 병합하는 방법은 무엇입니까? [닫은]
이것은 인터뷰에서 나에게 물었고 이것은 내가 제공 한 솔루션입니다.
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;
}
더 효율적인 방법이 있습니까?
편집 : 수정 된 길이 방법.
약간의 개선이 있었지만 메인 루프 후에 System.arraycopy는 다른 쪽 끝에 도달했을 때 입력 배열의 꼬리를 복사하는 데 사용할 수 있습니다 . O(n)그래도 솔루션 의 성능 특성은 변경되지 않습니다 .
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 루프의 단일 명령문에서 수행됩니다!
- 두 배열의 크기가 거의 같으면 O (n)의 상수는 동일합니다. 그러나 배열이 실제로 불균형하면
System.arraycopy내부적으로 단일 x86 어셈블리 명령어로이를 수행 할 수 있기 때문에 버전 이 승리합니다. a[i] >= b[j]대신에 유의하십시오a[i] > b[j]. 이것은 a와 b의 요소가 같을 때 정의되는 "안정성"을 보장하며, b 이전의 요소를 원합니다.
수행 할 수있는 모든 개선 사항은 미세 최적화이며 전체 알고리즘이 정확합니다.
이 솔루션은 System.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)
자바 스크립트로 작성해야했습니다. 여기 있습니다 :
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;
}
아파치 컬렉션은 버전 4부터 collate 메소드를 지원합니다. 다음 collate방법을 사용하여이 작업을 수행 할 수 있습니다 .
org.apache.commons.collections4.CollectionUtils
다음은 javadoc에서 인용 한 것입니다.
collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)비교기 c에 따라 요소의 순서가 유지되도록 두 개의 정렬 된 콜렉션
a과b를 하나의 정렬 된 목록으로 병합 합니다.
바퀴를 다시 발명하지 마십시오! 문서 참조 : http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html
GallopSearch 병합 : O (n) 대신 O (log (n) * log (i) )
나는 의견에 회색 수염 제안을 이행했습니다. 주로이 코드의 매우 효율적인 미션 크리티컬 버전이 필요했기 때문입니다.
- 이 코드는 O (log (i)) 인 gallopSearch를 사용합니다. 여기서 i는 현재 색인에서 관련 색인이 존재하는 거리입니다.
- 이 코드는 갤럽 검색에서 적절한 범위를 식별 한 후 이진 검색을 사용합니다. 갤럽이이를 더 작은 범위로 제한했기 때문에 결과 binarySearch도 O (log (i))입니다.
- 갤럽 및 병합은 거꾸로 수행됩니다. 이것은 미션 크리티컬 한 것처럼 보이지 않지만 배열을 병합 할 수 있습니다. 배열 중 하나에 결과 값을 저장할 공간이 충분하면 병합 배열 및 결과 배열 로 간단히 사용할 수 있습니다 . 이 경우 배열 내에 유효한 범위를 지정해야합니다.
- 이 경우 메모리 할당이 필요하지 않습니다 (중요한 작업에서 크게 절약). 단순히 처리되지 않은 값을 덮어 쓸 수 없으며 덮어 쓸 수 없습니다 (뒤로 만 가능). 실제로 입력과 결과 모두에 동일한 배열을 사용합니다. 아무런 영향을 미치지 않습니다.
- 나는 Integer.compare ()를 일관되게 사용하여 다른 목적으로 전환 할 수있었습니다.
- 내가 약간 증명했을 수도 있고 내가 이전에 입증 한 정보를 활용하지 못할 수도 있습니다. 하나의 값이 이미 확인 된 두 값의 범위로 이진 검색과 같은. 메인 루프를 명시하는 더 좋은 방법이있을 수도 있습니다. 뒤집기 c 값이 순서대로 두 개의 연산으로 결합되면 필요하지 않습니다. 당신은 당신이 매번 다른 하나를 할 것을 알고 있기 때문에. 광택을 내야 할 여지가 있습니다.
이것은 O (n)이 아니라 O (log (n) * log (i))의 시간 복잡성을 갖는 가장 효율적인 방법이어야합니다 . 그리고 최악의 경우 시간 복잡도 O (n). 배열이 울퉁불퉁하고 값이 긴 문자열을 사용하면 다른 방법을 사용할 수 없습니다. 그렇지 않으면 배열보다 낫습니다.
병합 배열의 끝에는 두 개의 읽기 값과 결과 배열 내의 쓰기 값이 있습니다. 어떤 값이 더 작은 지 알아 낸 후에는 해당 배열로 갤럽 검색을 수행합니다. 1, 2, 4, 8, 16, 32 등. 다른 배열의 읽기 값이 더 큰 범위를 찾으면. 이진은 해당 범위로 검색합니다 (범위를 반으로 자르고 올바른 반을 검색하며 단일 값까지 반복). 그런 다음 해당 값을 쓰기 위치에 복사합니다. 사본은 필연적으로 하나의 판독 배열에서 동일한 값을 덮어 쓸 수 없도록 이동합니다 (이는 기록 배열과 판독 배열이 동일 할 수 있음). 그런 다음 다른 어레이에 대해 동일한 작업을 수행하여 다른 어레이의 새로운 읽기 값보다 작은 것으로 알려져 있습니다.
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;
}
업데이트 : 이전 답변, 끔찍한 코드는 아니지만 위의 것보다 분명히 열등합니다.
또 다른 불필요한 하이퍼 최적화. 종료 비트뿐만 아니라 시작 비트에 대해서도 arraycopy를 호출합니다. binarySearch를 사용하여 O (log (n))의 소개 비 중첩을 데이터로 처리합니다. O (log (n) + n)은 O (n)이며 어떤 경우에는 병합 배열간에 겹치지 않는 부분과 같은 효과가 특히 두드러집니다.
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;
}
다음은 자바 스크립트로 작성된 단축 양식입니다.
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]or인지 확인하는 것이 합리적 b[n-1]<a[0]입니다. 이러한 경우에는 더 이상 비교할 필요가 없습니다. 알고리즘은 소스 배열을 결과 순서대로 올바른 순서로 복사 할 수 있습니다.
더 복잡한 개선 사항에는 인터리빙 부품 검색 및 병합 알고리즘 실행 만 포함될 수 있습니다. 병합 된 어레이의 크기가 점수에 따라 다를 때 많은 시간을 절약 할 수 있습니다.
이 문제는 두 개의 정렬 된 하위 배열이 단일 정렬 된 하위 배열로 결합되는 mergesort 알고리즘과 관련이 있습니다. CLRS의 책은 알고리즘의 일례를 제공하고 결국 각 어레이의 단부 (비교 무언가 "이외의 값보다 큰"참조) 센티널 값을 추가하여 도달하는 경우 검사에 대한 필요성을 정리.
나는 이것을 파이썬으로 작성했지만 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 개의 스레드를 사용하여 결과 배열을 채울 수 있습니다 (앞에서 하나씩, 뒤에서 하나씩).
이것은 각 스레드가 값의 절반을 삽입하는 경우와 같이 숫자의 경우 동기화없이 작동 할 수 있습니다.
//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;
});
};
내가 가장 좋아하는 프로그래밍 언어는 JavaScript입니다
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;
}
아마도 System.arraycopy를 사용하십시오.
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,
삼항 연산자를 사용하여 코드를 좀 더 컴팩트하게 만들 수 있습니다
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) 시간 복잡성에서 두 개의 정렬 된 배열을 결합하려면 하나의 루프에서만 아래 방법을 사용하십시오. 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 배열 사용 : import numpy
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
반응형
'IT' 카테고리의 다른 글
| hashCode에서 소수를 사용하는 이유는 무엇입니까? (0) | 2020.06.05 |
|---|---|
| dequeueReusableCellWithIdentifier와 dequeueReusableCellWithIdentifier를 사용하는 경우 : forIndexPath (0) | 2020.06.05 |
| bs4.FeatureNotFound : 요청한 기능이 포함 된 트리 빌더를 찾을 수 없습니다 : lxml. (0) | 2020.06.05 |
| 스타일 시트로 해석되었지만 MIME 유형 text / html로 전송 된 자원 (웹 서버와 관련이없는 것으로 간주 됨) (0) | 2020.06.05 |
| 데이터베이스에서 레코드를 버전 관리하는 방법 (0) | 2020.06.05 |