이것은 인터뷰에서 나에게 물었고 이것은 내가 제공 한 솔루션입니다.
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)