聯盟陣列

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++]); 
} 

相同的代碼將使用最少的變化路口工作....