Unie van twee arrays

Gegeven twee arrays

int arr1[n]
int arr2[m]

where n > m

Moet een unie van twee arrays in één schrijven.

Als de invoerarrays bijvoorbeeld zijn:

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

Then program should create new array Union as {1, 2, 3, 4, 5, 6, 7}

Implementatie kan in C# of Java zijn.

Om dit op te lossen, moet je eerst de arrays sorteren met behulp van Merge Sort en doe dan de verbintenis

Ik keek in het net maar vond de elegante manier niet. Elke code die ik eruit zag zat vol met IF's.

Advies alstublieft wat de snelste en meest elegante manier is om het te doen

0
Wat is de implementatietaal?
toegevoegd de auteur DwB, de bron
Wat zijn uw veronderstellingen? Denkt u aan de arrays als sets of zijn herhalingen toegestaan? Moet het resultaat worden gesorteerd?
toegevoegd de auteur PengOne, de bron
Er is niets inherent onelegant met if statements.
toegevoegd de auteur PengOne, de bron

5 antwoord

U hebt gelijk dat het samenvoegen van de twee lijsten zoals gedaan is in Samenvoeg sorteren het meest efficiënt is om te doen . Dit veronderstelt dat de twee lijsten al zijn gesorteerd, zoals in uw voorbeeld. Hier is een voorbeeld van hoe merge te implementeren:

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

Vanaf hier zijn eenvoudigweg geen herhalingen opgenomen in de uiteindelijke uitvoer.

4
toegevoegd
Kun je C# of Java-code plaatsen?
toegevoegd de auteur Gregory Nozik, de bron
Waar verhoog je links naar rechts?
toegevoegd de auteur Gregory Nozik, de bron

Als het een elegante MergeSort is, dan is niets eleganter dan een recursieve functie :-)

Hier is het :

Dit is een verdeel en heers strategie. We verdelen de array in feite in kleinere arrays, sorteren de kleinere arrays en voegen ze weer samen.

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

Niet veel ifs ook ..

Bron: mijn blog (http://cloudingitup.blogspot.com/p/reading-guide-arrays.html)

Om ze samen te voegen als een Unie:

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

}

Een stuurprogrammacode om de code te illustreren:

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

Uitgang: 12345678

2
toegevoegd
Het is geweldig, maar nawoord is het nodig om unie van arrays te maken
toegevoegd de auteur Gregory Nozik, de bron
nou deze heeft wat ifs: -O
toegevoegd de auteur srini, de bron
public static void printUnion(int ar1[],int ar2[]) {
        int m = ar1.length;
        int n = ar2.length;
        int i=0,j=0;

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

Dezelfde code werkt voor kruispunten met minimale wijzigingen ....

1
toegevoegd

deze methode zou redelijk goed moeten werken, en het zal beslissen welke array groter is, dus er hoeft niet noodzakelijkerwijs een gedefinieerde volgorde te zijn.

Java:

public static  T[] combine(T[] a1, T[] a2)
{
    return combine(a1, a2, a1.length + a2.length);
}
public static  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;
}

dit is duidelijk niet de meest efficiënte methode, maar het werkt volledig. Het bevat ook een capping, als je ze wilt samenvoegen, maar alleen de eerste, let's way 5 items krijgt, dan kun je een parameter van 5 aan de methode toevoegen.

Je kunt echt veel verspilling kwijtraken, er zijn hier heel veel rommel, ik ben weg van mijn IDE dus het is uit mijn hoofd, ik heb misschien dingen die niet nodig zijn.

0
toegevoegd

In interviews willen ze meestal dat je het probleem oplost, in plaats van het gebruik van bibliotheekoproepen (bijvoorbeeld arr1.union (arr2) zou het waarschijnlijk niet verminderen.)

Dit is de top van mijn hoofd, maar zoiets zou moeten werken, en ik denk dat het O (n ^ 2) is. Er wordt van uitgegaan dat beide matrices zijn gesorteerd.

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)
0
toegevoegd