Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Removing duplicates from a 1D array

array

  • Please log in to reply
8 replies to this topic

#1 Hiche

Hiche

    CC Lurker

  • Just Joined
  • Pip
  • 9 posts

Posted 30 November 2011 - 02:32 PM

I'm finding this hard to implement. So basically I want to remove the elements (integers) in an array that are duplicates (repeated more than twice). We cannot use any external class but the Arrays class (not the ArrayList etc).

Any guidance is appreciated. Thank you.
  • 0

#2 lethalwire

lethalwire

    while(false){ ... }

  • Senior Member
  • PipPipPipPipPipPip
  • 766 posts
  • Programming Language:C, Java, PHP, JavaScript
  • Learning:PHP

Posted 30 November 2011 - 04:45 PM

How about sorting the array using java.util.Arrays. Then iterating through removing the duplicates. (The duplicates should now be next to eachother)
  • 0

#3 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 30 November 2011 - 11:08 PM

Put it in a Set, and then back to a List :D
Okay, ignore the above. Like lethalwire said wouldn't be a bad idea.

Just write a utility method which removes something from the given array at index x to help yourself:
public void removeElement(int[] array, int index){

}

  • 0

#4 Perigren

Perigren

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 01 December 2011 - 08:01 AM

I'm giving it a shot right now and I've found what can be helpful is writing a method that creates an int array of all the numbers that have duplicates in the original array. For example if the original array was {2,2,2,3,4,6,6,6,7,7,8,9}, this method would return {2,6,7}.
  • 0

#5 Hiche

Hiche

    CC Lurker

  • Just Joined
  • Pip
  • 9 posts

Posted 01 December 2011 - 10:11 AM

My problem is removing the duplicates from the array. After I sort them (I used Array.sort(array)), how exactly do I iterate over them AND remove them? If the duplicates are next to each other, then what? Sorry for my ignorance that might render you impatient at a point.

Before looking at the replies, I came up with this:

for (int i = 0; i < array.length; i++)
    	{
    		for (int j = i + 1; j < array.length; j++)
    		{
    			if (i != j && array[i] == array[j])
    			{
    				// here's where I want to remove the duplicates
    			}
    		}
    	}

I iterate over the elements and if a duplicate of an integer is found, I want to remove it. For a better view on the problem statement, here it is:

Write a program RemoveDuplicates.java that takes three file names as command line arguments. The first two files contain a list of integers (the first line of each file contain the number of integers in that file). Your program should write to the third file the union of the numbers in the first two files (without any duplicates). Hint: Store the contents of the files in arrays first.

Taking three file names isn't important now. Just suppose the arguments are arrays. Also, just for clarification, merging two arrays is as follows, right?:
public static int[] merge(int[] array1, int[] array2)
    {
    	int[] array3 = new int[array1.length + array2.length];
    	for (int i = 0; i < array1.length; i++)
    		array3[i] = array1[i];
    	for (int j = 0; j < array2.length; j++)
    		array3[array1.length + j] = array2[j]; 	
    	return array3;
    }

Thank you for the replies.
  • 0

#6 lethalwire

lethalwire

    while(false){ ... }

  • Senior Member
  • PipPipPipPipPipPip
  • 766 posts
  • Programming Language:C, Java, PHP, JavaScript
  • Learning:PHP

Posted 01 December 2011 - 11:40 AM

If that's the case, you can insert all of the integers from the first file into the array but don't add any integer that is ALREADY in the array(java.util.Arrays.binarySearch(...). Then do the same for the other file.
The only "difficult" part of the task is inserting integers in place, and shifting values in the array.

If you do this, you won't have the problem of removing duplicate items from the array. I would take the first strategy over this one because if you have an array of:
[1,1,2,3,4,4]
Then you'd have to remove a 1, and a 4. But you can't technically remove them without creating a new array. OR you'd have to set the values to something like : Integer.MIN_VALUE or Integer.MAX_VALUE;
Then when you wanted to add the numbers to the third file, you'd have to use a check of:
if(array[i]==Integer.MIN_VALUE)
   skip this and don't add


Errr.. I guess either approach is fairly simple. :P
  • 0

#7 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 02 December 2011 - 03:32 AM

Just to re-enforce what lethalwire was saying; it is easiest with an insertinplace method and a binary search method. And you only need one array.
Algorithm:
load the array with the contents of the two files

for(int i = lo + 1; i <= array.length-1; i++)
 {
        if  (   ! binarySearch(on the array for value i; from lo to i)    )
       array = insertInPlace(array,0,i-1, array[i]);
 }

  • 0

#8 Ritwik I the programmer

Ritwik I the programmer

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 244 posts
  • Programming Language:Java
  • Learning:Java, C++, Python

Posted 04 December 2011 - 05:38 AM

OK, you need a down to earth version? try this:
//Duplicate element deletion array
import java.util.*;
class Duplication
{
    private int arr[];
    public void get()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter array size:");
        int size = sc.nextInt();
        arr = new int [size];
        for(int i = 0; i < size; i++)
        {
            System.out.println("Enter array element:");
            arr[i] = sc.nextInt();
        }
        System.out.println("Original Array:");
        show();
        delete();
        System.out.println("Duplicate deleted array:");
        show();
    }
    public void delete()
    {
        int size = arr.length;
        for(int i = 0; i < size; i++)
        {
            for(int j = i + 1; j < size; j++)
            {
                while(arr[i] == arr[j])
                {
                    for(int k = j; k < size - 1; k++)
                        arr[k] = arr[k + 1];
                    size--;
                    if(j == size) break;
                }
            }
        }
        int t[] = new int[size];
        for(int l = 0; l < size; l++)
            t[l] = arr[l];
        arr = t;
    }
    public void show()
    {
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}
public class Duplication_main
{
   public static void main(String  args[])
   {
       Duplication d = new Duplication();
       d.get();
   }
}

  • 0

#9 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 04 December 2011 - 06:01 AM

...OK, you need a down to earth version?...

You nest loops four layers deep and use two arrays. I really don't see how this is much different from what we were explaining. I will like to see the performance if the files had 10000 numbers each :w00t:.

Note: this could be done without nesting a single loop, one array and you end up with a sorted list.
  • 1





Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download