两个数组的并集

本文关键字：数组 两个 | 更新日期: 2023-09-27 18:16:53

给定两个数组

int arr1[n]
int arr2[m]

其中n>m

需要将两个数组的并集写入一个数组。

例如，如果输入数组为：

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

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

实现可以是C#或Java。

为了解决这个问题，首先需要使用合并排序对数组进行排序然后进行联合

我看了看网，但没有找到优雅的方式。我看的每一个代码到处都是IF。

请建议什么是最快速、最优雅的方法

两个数组的并集

您正确地认为，按照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

从这里开始，不要在最终输出中包含重复。

如果你正在寻找一个优雅的MergeSort，那么没有什么比递归函数更优雅了：-(

这是：

这是一种分而治之的策略。我们基本上将数组划分为较小的数组，对较小的数组进行排序，然后将它们合并回来。

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

如果也不多。。

来源：我的博客(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

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

相同的代码将适用于变化最小的交叉口。。。。

在面试中，他们通常希望看到你解决问题，而不是使用库调用(例如arr1.union(arr2)可能无法解决问题。(

这是我的想法，但像这样的东西应该工作，我认为是O(n^2(。它假定两个数组都已排序。

union.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)

这个方法应该可以很好地工作，它将决定哪个数组更大，因此不必有定义的顺序。

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，所以我不想去，我可能有不需要的东西。

相关文章：