java 在不使用额外空间的情况下合并两个数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4903585/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Merging two arrays without using extra space
提问by algorithmX
I have 2 sorted arrays, a1and a2, of lengths l1and l2, respectively. The array a2has empty space at the end of length l1, so it can hold all of the elements of a1in addition to its own elements. Now, I want to merge a1into a2so that a2will contain all the elements of a1and a2in sorted order. Ideally this should use O(1) auxiliary storage space. I have the following cod,e but something is going wrong:
我有 2 个排序的数组，a1and a2，长度分别为l1和l2。该数组a2在 length 的末尾有空白空间l1，因此a1除了它自己的元素之外，它可以容纳 的所有元素。现在，我要合并a1到a2，这样a2将包含的所有元素a1，并a2在排序顺序。理想情况下，这应该使用 O(1) 辅助存储空间。我有以下鳕鱼，但出了点问题：
public static int[] merge(int []a1,int a2[],int l1, int l2){
System.out.println("l1 =" +l1 + " l2=" +l2);
int es = l2-l1;
int fs = l2-es;
System.out.println("es= " +es);
System.out.println("fs = " + fs);
int j=0;
for(int i=0;i< l1;i++){
if(j<fs){
// System.out.println("i= " + i + "a1[i]=" + a1[i]);
// System.out.println("j= " + j + "a2[j]=" + a2[j]);
if(a1[i]<a2[j]){
add(a2,j,a1[i],l2);
//i++;
fs++;
}
}else{
System.out.println("***");
a2[j]=a1[i];
}
j++;
}
return a2;
}
public static void add(int []a,int p,int key,int l){
for(int i=l-1;i>p;i--){
a[i]= a[i-1];
}
a[p]= key;
}
Does anyone have any ideas on how to fix this? I used following data to run the code:
有没有人对如何解决这个问题有任何想法？我使用以下数据来运行代码：
int a1[]= new int[]{-1,0,7,8};
int a2[]= new int[7];
a2[0]=1;
a2[1]=3;
a2[2]=9;
Output is
输出是
l1 =4 l2=7
es= 3
fs = 4
-1
0
1
3
9
0
0
回答by Nikita Rybak
It's difficult to tell what your code does, but it seems to have suboptimal (O(n^2)) complexity: there's a second loop inside addmethod.
Also, note that fsis always equal to l1.
很难说你的代码做了什么，但它似乎有次优 ( O(n^2)) 复杂性：add方法内部有第二个循环。
另外，请注意fs总是等于l1。
But there's much simpler method: from the back. If you think about it, there's always enough space.
但是有更简单的方法：从后面。仔细想想，总有足够的空间。
Something like this
像这样的东西
int i = l1 - 1;
int j = l2 - 1;
int result_pos = l1 + l2 - 1;
while (i >= 0 || j >= 0) {
if (a1[i] >= a2[j]) {
a2[result_pos--] = a1[i--];
} else {
a2[result_pos--] = a2[j--];
}
}
PS You'll need to add handling for the case when one of iand jis negative in the loop. Obviously, in this case another element should be copied.
PS当循环中的一个i和j为负时，您需要为这种情况添加处理。显然，在这种情况下，应该复制另一个元素。
edit
Later can be done with this condition
编辑
以后可以用这个条件完成
if (j < 0 || (i >= 0 && a1[i] >= a2[j])) {
instead of
代替
if (a1[i] >= a2[j]) {
回答by Argote
If the elements in a1and a2are sorted then you'd have something like this:
如果a1和a2中的元素被排序，那么你会有这样的事情：
a1 : [-1] [0] [7] [8]
a2 : [1] [3] [9] [] [] [] []
So in code you can do this:
所以在代码中你可以这样做：
int a1i = 0; // pointer to the ith element in the array a1
int tmp = 0;
int i = 0;
for(i = 0; i < a1.length; i++) {
if(a2[i] > a1[a1i]) {
tmp = a2[i];
a2[i] = a1[a1i];
a1[a1i] = tmp;
Arrays.sort(a1); // This might take more memory though...
} else {
a1i++;
}
}
a1i = 0;
for(i; i < a2.length; i++) {
a2[i] = a1[a1i];
a1i++;
}
This would work out to:
这将适用于：
a1 : [-1] [0] [7] [8]
^
a2 : [1] [3] [9] [] [] [] []
^
SWAP
a1 : [1] [0] [7] [8]
^
a2 : [-1] [3] [9] [] [] [] []
^
SORT
a1 : [0] [1] [7] [8]
^
a2 : [-1] [3] [9] [] [] [] []
^
SWAP
a1 : [3] [1] [7] [8]
^
a2 : [-1] [0] [9] [] [] [] []
^
SORT
a1 : [1] [3] [7] [8]
^
a2 : [-1] [0] [9] [] [] [] []
^
SWAP
a1 : [9] [3] [7] [8]
^
a2 : [-1] [0] [1] [] [] [] []
^
SORT
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [] [] [] []
^
COPY
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [3] [] [] []
^
COPY
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [3] [7] [] []
^
COPY
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [3] [7] [8] []
^
COPY
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [3] [7] [8] [9]
^
END
回答by jonderry
First, shift the elements of a1 to the back of a1. Second merge a1 and a2 starting the front of a1 (i.e., write the minimum of the two elements being compared to the current index in a1, where the current index starts at 0 and ranges up to a1.length + a2.length - 1). This will prevent you from overwriting any elements of a1.
首先，将 a1 的元素移到 a1 的后面。第二次合并 a1 和 a2 从 a1 的前面开始（即，在 a1 中写入与当前索引进行比较的两个元素的最小值，其中当前索引从 0 开始，范围最大为 a1.length + a2.length - 1） . 这将防止您覆盖 a1 的任何元素。
回答by algorithmX
There are many good answers. I just wanted to add something (the comments are already so buried):
有很多很好的答案。我只是想补充一点（评论已经被埋没了）：
This is just the merging phase of a merge-sortor similar such as a k-way sort.Just use an in-place merge routine. Either the "smaller array" or the "empty space" can be used to store values in the "larger array" which are not currently in sort-order.
这只是合并排序或类似排序（例如k-way sort ）的合并阶段。只需使用就地合并例程。“较小数组”或“空白空间”均可用于将值存储在“较大数组”中，这些值当前未按排序顺序排列。
It's okay to borrow bits and pieces of different algorithms :-)
可以借用不同算法的点点滴滴:-)
回答by 9000
I'd start merging from the end.
我会从最后开始合并。
At the last element, put max(lastOf(a1), lastOf(f2)). Continue to bite off one element at a time from the rest of either array, until one of these is exhausted. Put the rest of the remaining array to the start (may me a no-op).
在最后一个元素处，放置max(lastOf(a1), lastOf(f2)). 继续从任一数组的其余部分一次咬掉一个元素，直到其中一个被耗尽。将剩余数组的其余部分放在开头（请允许我不要操作）。
回答by Abbas
I assume you have no restriction on time complexity of your algorithm. My suggestion is to append the values of a1 to a2 and apply any O(nlogn) sorting algorithm like quicksort. However if you'd like to do the merging, i think this code helps you:
我假设您对算法的时间复杂度没有限制。我的建议是将 a1 的值附加到 a2 并应用任何 O(nlogn) 排序算法，如快速排序。但是，如果您想进行合并，我认为此代码可以帮助您：
public static void main(String[] args) {
// TODO Auto-generated method stub
int a1[]= new int[]{-1,0,7,8};
int a2[]= new int[7];
a2[0]=1;
a2[1]=3;
a2[2]=9;
merge(a1, a2, 3);
}
private static void merge(int[] a1, int[] a2, int lastPos) {
for ( int i = 0; i < a1.length; i++)
{
for ( int j = 0; j < a2.length; j++)
if ( a1[i] < a2[j] )
{
add(a1[i], a2, j, lastPos);
lastPos++;
break; //since a2 is also sorted
}
}
}
private static void add(int val, int[] a2, int j, int lastPos) {
for ( int i = lastPos; i > j; i--)
a2[i] = a2[i-1];
a2[j] = val;
}
回答by Rezwan4029
Merge Two Sorted Array Without Using Extra Memory
在不使用额外内存的情况下合并两个已排序的数组
#include<iostream>
using namespace std ;
const int N = 100 ;
int a[N] , b[N] , n , m , len , L ;
int main() {
cin >> n ;
for( int i = 0 ; i < n ; i++ ) cin >> a[i] ;
cin >> m ;
for( int i = 0 ; i < m ; i++ ) cin >> b[i] ;
len = n + m - 1 ;
L = n + m ;
n-- , m-- ;
while( len >= 0 ) {
if( m < 0 ) a[len] = a[n--];
else if( n < 0 ) a[len] = b[m--];
else if( a[n] > b[m] ) a[len] = a[n--];
else a[len] = b[m--];
len--;
}
for( int i = 0 ; i < L ; i++ ) cout << a[i] << " " ;
}
回答by craftsmannadeem
This is nothing but merge phase of merge sort,
这只不过是归并排序的归并阶段，
- copy all the elements of a2
(1,2,3,4)at the end of a1(5,6,7,8), now a1 will contain(4,5,6,7,8,1,2,3,4) - Now invoke the merge algorithm below
inPlaceMerge(collection, 0<low>,3<mid>,7<high>);
(1,2,3,4)在 a1 的末尾复制 a2 的所有元素(5,6,7,8)，现在 a1 将包含(4,5,6,7,8,1,2,3,4)- 现在调用下面的合并算法
inPlaceMerge(collection, 0<low>,3<mid>,7<high>);
here is the algorithm in Java,
这是Java中的算法，
public static <T extends Comparable<? super T>> void inPlaceMerge(T[] collection, int low, int mid, int high) {
int left = low;
int right = mid + 1;
if(collection[mid].equals(collection[right])) {
return ;//Skip the merge if required
}
while (left <= mid && right <= high) {
// Select from left: no change, just advance left
if (collection[left].compareTo(collection[right]) <= 0) {
left ++;
} else { // Select from right: rotate [left..right] and correct
T tmp = collection[right]; // Will move to [left]
rotateRight(collection, left, right - left);
collection[left] = tmp;
// EVERYTHING has moved up by one
left ++; right ++; mid ++;
}
}
}
private static <T extends Comparable<? super T>> void rotateRight(T[] collection, int left, int numberOfElements) {
System.arraycopy(collection, left, collection, left+1, numberOfElements);
}
Here is the unit test
这是单元测试
@Test
public void inPlaceMergeFirstTest() {
Integer[] collection = new Integer[]{5,6,7,8,1,2,3,4};
ArrayUtils.<Integer>inPlaceMerge(collection, 0,3,7);
Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
assertThat(collection, equalTo(result));
}
回答by dimpy aggarwal
The better way to solve the question is used to Insertion sort for merging two sorted arrays in O(1) auxiliary space.
更好的解决方法是使用插入排序在 O(1) 辅助空间中合并两个已排序的数组。
/* as we have to merge the 2 sorted arrays in array2. we begin from the end of array2 and insert the array element at its correct position acc. to insertion sort*/
/* 因为我们必须合并 array2 中的 2 个排序数组。我们从 array2 的末尾开始，并在其正确位置 acc 插入数组元素。插入排序*/
public static int[] merge(int []a1,int a2[],int l1, int l2){
int len2=l2-l1;
for(int i=l1-1;i>=0;i--){
int j=len2-1;
for(;j>=0 && j+1<l2 && a2[j]>a[i];j--){
a2[j+1]=a2[j];
}
a2[j+1]=a1[i];
len2++;
}
}
回答by dimpy aggarwal
/or simply you can do this->/
/或者干脆你可以这样做->/
public static int[] merge(int []a1,int a2[],int l1, int l2){
int j=0;
for(int i=l2-l1;i<l2;i++)
{
a2[i]=a1[j];
j++;
}
Arrays.sort(a2);
return a2;
}
