联盟阵列

Question

给定两个阵列

int arr1[n] 
int arr2[m] 

其中N> M

需要两个阵列的联合写入之一。

例如，如果输入的数组是：

int arr1[] = {1, 3, 4, 5, 7} 
    int arr2[] = {2, 3, 5, 6} 

然后程序应该创建新的数组联盟作为{1, 2, 3, 4, 5, 6, 7}

实现可以是在C＃或Java。

为了首先要解决它需要使用合并数组排序排序 然后做工会

我看着在网，但没有找到优雅的方式。我看到的所有代码都是IF的。

请咨询什么是最快速和优雅的方式来做到这一点

Answer 1

你是正确的，合并两个列表作为在Merge Sort做的是做的最有效的事情。这假设这两个列表已经排序，如你的例子。这里是一个如何实现合并的例子：

function merge(left,right) 
    var list result 
    while length(left) > 0 or length(right) > 0 
     if length(left) > 0 and length(right) > 0 
      if first(left) ≤ first(right) 
       append first(left) to result 
       left = rest(left) 
      else 
       append first(right) to result 
       right = rest(right) 
     else if length(left) > 0 
      append first(left) to result 
      left = rest(left) 
     else if length(right) > 0 
      append first(right) to result 
      right = rest(right) 
    end while 
    return result 

从这里，根本不包括重复在最终输出。

Answer 2

如果你正在寻找一个优雅的归并再没有什么比:-)

这是一个递归函数更优雅：

这是一种分而治之的策略。我们基本上把数组分成更小的数组，排序更小的数组并将它们合并回来。

public static void mergesort(int a[],int left, int right){ 
    /* 
    * Time : O(n log n) 
    * Space : O(n) 
    */ 
    int b[] = new int[right -left+1]; 
    domergesort(a,left,right,b); 
} 

public static void domergesort(int a[],int left,int right, int b[]){ 

    if(left < right){ 
     int mid = (left+right)/2; 
     domergesort(a,left,mid,b); 
     domergesort(a,mid+1,right,b); 
     merge(a,left,mid,a,mid+1,right,b); 
     for(int k=left;k<=right;k++) 
      a[k] = b[k-left]; 
    } 
} 

没有多少IFS太..

来源：我的博客（http://cloudingitup.blogspot.com/p/reading-guide-arrays.html）

要它们合并起来作为联：

public static void merge(int a[], int al, int ar, int b[], int bl, int br, int c[]){ 
    // al : a's left index ar : a's right index c: merged array 
    int i= al; 
    int j = bl; 
    int k=0; 
    int prev = c[0]; 

    while (i<= ar && j <= br){ 
     if (a[i] <= b[j]) 
      if (prev != a[i]) // Too keep the union distinct 
       c[k++] = a[i++]; 
      else 
      i++; 
     else 
      if (prev != b[j]) // Too keep the union distinct 
       c[k++] = b[j++]; 
      else 
       j++; 

     prev = c[k-1]; 

    } 

    while (i <= ar) 
    { 
    if (prev != a[i]) 
     c[k++] = a[i++]; 
     else 
     i++; 

     prev = c[k-1]; 
     } 


    while (j <= br) 
    { 
    if (prev != b[j]) 
     c[k++] = b[j++]; 
     else 
     j++; 
     prev = c[k-1]; 
     } 

} 

驾驶员代码来说明的代码：

int arr1[] = {1,1, 3, 4,4,4,5, 7}; 
int arr2[] = {2, 3, 5, 6,6,8}; 
int c[] = new int[8]; 

merge(arr1,0,7,arr2,0,5,c); 

for(int i=0;i<8;i++) 
System.out.print(c[i]); 

输出：12345678

Answer 3

在采访中，他们通常希望看到您解决问题，而不是使用库调用（例如， arr1.union(arr2)可能不会削减它。）

这是关闭我的头顶，但这样的事情应该工作，我认为是O（n^2）。它假定两个数组都是排序的。

联合。RB

arr1 = [0,2,4,9,11,12,13] 
arr2 = [3,4,7,9,10,11] 

def union(n, m) 
    if n.last > m.last 
    arr1 = n; arr2 = m 
    else 
    arr1 = m; arr2 = n 
    end 

    union_array = [] 
    j = 0 
    arr1.each do |x| 
    while j < arr2.length && arr2[j] < x 
     if arr2[j] < x 
     union_array << arr2[j] unless arr2[j] == union_array.last 
     j += 1 
     end 
    end 
    union_array << x 
    end 
    union_array 
end 

puts union(arr1, arr2) 

Answer 4

这种方法应该工作得相当好，它会决定哪阵列较大所以并不需要一定是一个定义的顺序。

的Java：

public static <T> T[] combine(T[] a1, T[] a2) 
{ 
    return combine(a1, a2, a1.length + a2.length); 
} 
public static <T> T[] combine(T[] a1, T[] a2, int maxlength) 
{ 
    T[] front = null; 
    T[] back = null; 
    if(a1.length >= a2.length) 
    { 
     front = a1; 
     back = a2; 
    } 
    else 
    { 
     front = a2; 
     back = a1; 
    } 
    int len = front.length + back.length; 
    if(len > maxlength) 
    { 
     len = maxlength; 
    } 
    int n = 0; 
    T[] result = Arrays.copyOf(front, len); 
    int c = 0; 
    for(int i = 0;i < front.length;i++) 
    { 
     if(i < front.length && c < result.length) 
     { 
      result[c] = front[i]; 
      c++; 
     } 
     if(i < back.length && c < result.length) 
     { 
      result[c] = back[i]; 
      c++; 
     } 
    } 
    return result; 
} 

这显然不是最有效的方法，但它完全正常工作。它还包括一个上限，如果你想合并它们，但只得到第一个，让我们的方式5个项目，那么你可以添加一个参数5的方法。

你实际上可以摆脱很多浪费，这里有很多杂乱的东西，我远离我的IDE，所以它没有我的头，我可能有不需要的东西。

Answer 5

public static void printUnion(int ar1[],int ar2[]) { 
     int m = ar1.length; 
     int n = ar2.length; 
     int i=0,j=0; 

     while(i<m && j<n) { 
      if(ar1[i] <ar2[j]) { 
       System.out.println(ar1[i]); 
       i++; 
      }else if(ar1[i] > ar2[j]) { 
       System.out.println(ar2[j]); 
       j++; 
      }else { 
       System.out.println(ar1[i]); 
       i++; 
       j++; 
      } 
     } 
     while(i < m) 
       System.out.println(ar1[i++]); 
     while(j < n) 
       System.out.println(ar2[j++]); 
} 

相同的代码将使用最少的变化路口工作....