合并两个数组而不使用额外的空间
我有2个排序的数组， a1和a2 ，长度分别为l1和l2 。 数组a2在长度为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]p;i--){ a[i]= a[i-1]; } a[p]= key; }
有没有人对如何解决这个问题有任何想法？ 我使用以下数据来运行代码：
int a1[]= new int[]{-1,0,7,8}; int a2[]= new int[7]; a2[0]=1; a2[1]=3; a2[2]=9;
输出是
l1 =4 l2=7 es= 3 fs = 4 -1 0 1 3 9 0 0
很难说出你的代码做了什么，但似乎有一个次优（ O(n^2) ）的复杂性：在add方法中有第二个循环。
另请注意， fs始终等于l1 。
但是有更简单的方法：从后面开始。 如果你考虑一下，总有足够的空间。
像这样的东西
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当i和j中的一个在循环中为负时，您需要为该情况添加处理。 显然，在这种情况下，应该复制另一个元素。
编辑
以后可以用这个条件来完成
if (j < 0 || (i >= 0 && a1[i] >= a2[j])) {
代替
if (a1[i] >= a2[j]) {
如果a1和a2中的元素是排序的，那么你会有这样的东西：
a1 : [-1] [0] [7] [8] a2 : [1] [3] [9] [] [] [] []
所以在代码中你可以这样做：
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++; }
这可以解决：
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
首先，将a1的元素移到a1的后面。 第二次合并a1和a2从a1的前面开始（即，将两个元素中的最小值与a1中的当前索引进行比较，其中当前索引从0开始，范围最大为a1.length + a2.length – 1） 。 这将阻止您覆盖a1的任何元素。
我会从最后开始合并。
在最后一个元素处，输入max(lastOf(a1), lastOf(f2)) 。 继续从任一arrays的其余部分一次咬掉一个元素，直到其中一个元素耗尽。 将剩余的数组放在开头（可能是一个无操作）。
有很多好的答案。 我只想添加一些东西（评论已经被埋没了）：
这只是合并排序或类似的合并阶段，例如k-way排序 。 只需使用就地合并例程。 “较小arrays”或“空白空间”可用于在“较大arrays”中存储值，这些值当前不是排序顺序。
借用不同算法的点点滴滴是可以的:-)
为什么要编写自己的代码呢？ 如果a2有足够的空白空间来容纳a1的元素，只需将元素从a1复制到a2（使用arraycopy），然后使用Arrays.sort（）。 这会给你O（n * log（n）），而你的简单方法似乎也是O（n * n）。
（但是合并可以在O（n）中完成。）
我假设您对算法的时间复杂度没有限制。 我的建议是将a1的值附加到a2并应用任何O（nlogn）排序算法，如quicksort。 但是，如果您想进行合并，我认为此代码可以帮助您：
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; }
在不使用额外内存的情况下合并两个排序数组
#include 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] << " " ; }
这只是合并排序的合并阶段，
- 复制a1
(5,6,7,8)末尾a2(1,2,3,4)所有元素，现在a1将包含(4,5,6,7,8,1,2,3,4) - 现在调用
inPlaceMerge(collection, 0下面的合并算法,3 ,7 ); inPlaceMerge(collection, 0,3 ,7 );
这是Java中的算法，
public static > 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 > void rotateRight(T[] collection, int left, int numberOfElements) { System.arraycopy(collection, left, collection, left+1, numberOfElements); }
这是unit testing
@Test public void inPlaceMergeFirstTest() { Integer[] collection = new Integer[]{5,6,7,8,1,2,3,4}; ArrayUtils.inPlaceMerge(collection, 0,3,7); Integer[] result = new Integer[]{1,2,3,4,5,6,7,8}; assertThat(collection, equalTo(result)); }
你试过System.arrayCopy吗？ 就像是 ：
... System.arraycopy(a2, 0, a2, a1.length, a2.length); System.arraycopy(a1, 0, a1, 0, a1.length); ...
应该尽量不浪费时间（arraycopy针对这些用例进行了优化）。