Java - Merge Two Arrays without Duplicates (No lib

问题:

Need assistance with programming issue.

Must be in Java. Cannot use any libraries (Arraylist, etc.).

int[] a = {1, 2, 3, 4, 8, 5, 7, 9, 6, 0}
int[] b = {0, 2, 11, 12, 5, 6, 8}

Have to create an object referencing these two arrays in a method that merges them together, removes duplicates, and sorts them.

Here's my sort so far. Having difficulty combining two arrays and removing duplicates though.

int lastPos;
int index;
int temp;

for(lastPos = a.length - 1; lastPos >= 0; lastPos--) {
    for(index = 0; index <= lastPos - 1; index++) {
        if(a[index] > a[index+1]) {
            temp = a[index];
            a[index] = a[index+1];
            a[index+1] = temp;
        }
    }
}

回答1:

Merge Two Arrays without Duplicates and Sort it (No libraries used). Using an object.

public class MergeRemoveDupSort {    

public int[] mergeRemoveDupSortIt(int[] a, int[] b) {   
    int [] c = mergeIt(a,b);
    int [] d = removeIt(c);
    int [] e = sortIt(d);
    return e;
}

private int[] mergeIt(int[] a, int[] b) {   
    int[] c = new int[a.length + b.length];        
    int k=0;
    for (int n : a) c[k++]=n;        
    for (int n : b) c[k++]=n;   
    return c;
}

private int[] removeIt(int[] c) {  
    int len=c.length;
    for (int i=0;i<len-1;i++) 
        for (int j=i+1;j<len;j++)
            if (c[i] == c[j]) {
                for (int k=j;k<len-1;k++)
                    c[k]=c[k+1];
                --len;
            } 
    int [] r = new int[len];
    for (int i=0;i<r.length;i++)
        r[i]=c[i];
    return r;
}

private int[] sortIt(int[] a) {   
    for(int index=0; index<a.length-1; index++)
       for(int i=index+1; i<a.length; i++)
           if(a[index] > a[i]){
               int temp = a[index];
               a[index] = a[i];
               a[i] = temp;
           }
     return a;
}    

public void printIt(int[] a) {   
    System.out.print("[");
    for (int i=0;i<a.length;i++){
        System.out.print(a[i]);
        if (i!=a.length-1) System.out.print(",");
        else System.out.print("]");            
    }        
}

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 8, 5, 7, 9, 6, 0};
    int[] b = {0, 2, 11, 12, 5, 6, 8};

    MergeRemoveDupSort array = new MergeRemoveDupSort();
    int [] r = array.mergeRemoveDupSortIt(a, b);
    array.printIt(r);        
}        
}

回答2:

a method that merges them together, removes duplicates, and sorts them.

I suggest you break this down into helper methods (and slightly tweak the order of operations). Step 1, merge the two arrays. Something like,

static int[] mergeArrays(int[] a, int[] b) {
    int[] c = new int[a.length + b.length];
    for (int i = 0; i < a.length; i++) {
        c[i] = a[i];
    }
    for (int i = 0; i < b.length; i++) {
        c[a.length + i] = b[i];
    }
    return c;
}

Step 2, sort the new array (your existing sort algorithm is fine). Like,

static void sortArray(int[] a) {
    for (int lastPos = a.length - 1; lastPos >= 0; lastPos--) {
        for (int index = 0; index <= lastPos - 1; index++) {
            if (a[index] > a[index + 1]) {
                int temp = a[index];
                a[index] = a[index + 1];
                a[index + 1] = temp;
            }
        }
    }
}

Finally, remove duplicates. Step 3a, count unique values. Assume they're unique, and decrement by counting adjacent (and equal) values. Like,

static int countUniqueValues(int[] c) {
    int unique = c.length;
    for (int i = 0; i < c.length; i++) {
        while (i + 1 < c.length && c[i] == c[i + 1]) {
            i++;
            unique--;
        }
    }
    return unique;
}

Then step 3b, take the unique count and build your result with the previous methods. Like,

public static int[] mergeDedupSort(int[] a, int[] b) {
    int[] c = mergeArrays(a, b);
    sortArray(c);
    int unique = countUniqueValues(c);
    int[] d = new int[unique];
    int p = 0;
    for (int i = 0; i < c.length; i++) {
        d[p++] = c[i];
        while (i + 1 < c.length && c[i] == c[i + 1]) {
            i++;
        }
    }
    return d;
}

Then you can test it with your arrays like

public static void main(String[] args) {
    int[] a = { 1, 2, 3, 4, 8, 5, 7, 9, 6, 0 };
    int[] b = { 0, 2, 11, 12, 5, 6, 8 };
    int[] c = mergeDedupSort(a, b);
    System.out.println(Arrays.toString(c));
}

And I get

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12]

回答3:

You should use IntStream like this.

    int[] a = {1, 2, 3, 4, 8, 5, 7, 9, 6, 0};
    int[] b = {0, 2, 11, 12, 5, 6, 8};
    int[] merged = IntStream
        .concat(IntStream.of(a), IntStream.of(b))
        .distinct()
        .sorted()
        .toArray();
    System.out.println(Arrays.toString(merged));

回答4:

Assuming that array a and array b are sorted, the following code will merge them into a third array merged_array without duplicates :

public static int[] get_merged_array(int[] a, int[] b, int a_size, int b_size)
{

  int[] merged_array = new int[a_size + b_size];


  int i = 0 , j = 0, x = -1;

  for(; i < a_size && j < b_size;)
  {
      if(a[i] <= b[j])
      {
          merged_array[++x] = a[i];

          ++i;
      }
      else          
      {
          if(merged_array[x] != b[j])
          {
              merged_array[++x] = b[j]; // avoid duplicates
          }

          ++j;
      }
  }

  --i; --j;

  while(++i < a_size)
  {
       merged_array[++x] = a[i];
  }

  while(++j < b_size)
  {
      merged_array[++x] = b[j];
  }

  return merged_array;
}

Hope this may help, all the best :)

回答5:

    try{
    int[] a = {1, 2, 3, 4, 8, 5, 7, 9, 6, 0};
    int[] b = {0, 2, 11, 12, 5, 6, 8};
    int[] c = new int[a.length+b.length];
    int[] final = new int[a.length+b.length];
    int i = 0;
    for(int j : final){
        final[i++] = -1;
    }
    i = 0;
    for(int j : a){
        c[i++] = j;
    }
    for(int j : b){
        c[i++] = j;
    }
    boolean check = false;
    for(int j = 0,k = 0; j < c.length; j++){
        for(int l : fin){
            if( l == c[j] )
                check = true;
        }
        if(!check){
            final[k++] = c[j];
        } else check = false;
    }

} catch(Exception ex){
    ex.printStackTrace();
}

I prefer you to use Hashset for this cause it never allow duplicates and there is another method in java 8 for arraylist to remove duplicates after copying all elements to c follow this code

List<Integer> d = array.asList(c);
List<Integer> final = d.Stream().distinct().collect(Collectors.toList());
final.forEach(System.out::println());

This code is lot much better than previous one and you can again transform final to array like this

int array[] = new int[final.size()];              
    for(int j =0;j<final.size();j++){
      array[j] = final.get(j);
    }

Hope my work will be helpful .

回答6:

Let me restate your question.

You want a program that takes two arbitrary arrays, merges them removing any duplicates, and sorts the result.

First of all, if you have access to any data structure, there are much better ways of doing this. Ideally, you would use something like a TreeSet.

However, assuming all you have access to is arrays, your options are much more limited. I'm going to go ahead and assume that each of the two arrays initially has no duplicates.

Let's assume the first array is of length m and the second array is of length n.

int[] array1; // length m
int[] array2; // length n

First, let's sort both arrays.

Arrays.sort(array1);
Arrays.sort(array2);

This assumes you have access to the Arrays class which is part of the standard Java Collections Framework. If not, any reasonable merge implementation (like MergeSort) will do the trick.

The sorts will take O(n log n + m log m) with most good sort implementations.

Next, let's merge the two sorted arrays. First, we need to allocate a new array big enough to hold all the elements.

int[] array3 = new int[size];

Now, we will need to insert the elements of array1 and array2 in order, taking care not to insert any duplicates.

int index=0, next=0, i=0, j=0;
int last = Integer.MAX_INT;
while(i < m || j < n) {
    if(i == m)
        next = array2[j++];
    else if(j == n)
        next = array1[i++];
    else if(array1[i] <= array2[j])
        next = array1[i++];
    else
        next = array2[j++];

    if(last == next)
        continue;

    array3[index++] = next;
}

Now, you have your array. Just one problem - it could have invalid elements at the end. One last copy should take care of it...

int[] result = Arrays.copyOf(array3, index + 1);

The inserts and the final copy will take O(n + m), so the overall efficiency of the algorithm should be O(n log n + m log n).