By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
438,034 Members | 820 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 438,034 IT Pros & Developers. It's quick & easy.

Duplicate element in array

P: 13
I'm trying to create a method removedDuplicate() in which this method would find and remove a duplicated entry in an array of integers.

I would like any advice on how I would create this method.
Dec 2 '06 #1
Share this Question
Share on Google+
9 Replies


P: 32
one thing thats I find useful to do when working with arrays, if you're constructing them yourself, is to keep an integer value updated with the number of total useful entries in an array.

There are several ways to do this, your choice depends on whether you need to keep the elements in the same order they were given or whether their order does not matter.

Do you have any code that you've written yet?
Dec 2 '06 #2

P: 13
I first created this method that would search an array and would return the first element. How can I change this method to delete a duplicate entry?

Expand|Select|Wrap|Line Numbers
  1. public int findFirstElementLog(int [] arr,int x) {
  2.  
  3.             if(arr[0] == x ) {
  4.             count++;
  5.             return 0;
  6.         }
  7.  
  8.  
  9.             if(arr[arr.length - 1] == x && arr[arr.length - 2] != x ) {
  10.             count++;
  11.             return arr.length - 1;
  12.         }
  13.  
  14.  
  15.             if(arr[0] > x) {
  16.             count++;
  17.             return -1;
  18.         }
  19.  
  20.  
  21.             if( x < arr[0] || x > arr[arr.length - 1]){
  22.             count++;
  23.             return -1;
  24.         }
  25.  
  26.           return findFirstElement(arr, x, 0, 1, arr.length - 1); 
  27.     }
Dec 3 '06 #3

P: 32
ok i'm going to assume you can extrapolate code from description, since I dont want to write it for you.

This is much more efficient than the second way, but it might not be useful in this case, depending on the requirements:

Say you have an array[n], and you know that it only uses slots 0 to m, and the rest of the slots are not given useful values (they're either null or 0 by default).

If you do not know or are not given m, for object arrays this is easy to find (the null cells), for number arrays, there might be a range of cells that are supposed to be zero, so there is no simple check if you are not told where the useful data ends.

If you already know, are given, or are able to find, m and the order of the data in the array is not important, once you locate the duplicate, write the data from the last useful array slot on top of it and decrement m, you may also change the last value to null or zero, but if you're keeping track of m, it shouldnt matter.

if you have to generate a new array to be returned rather than change the contents of the old one, thats relatively easy, just don't write the value to the new array if its a duplicate.

The other way to do this, if you cannot discover the value of m, would be to shift all of the values to the "right" of the duplicate one space to the left, but this is less efficient. It is also better to do this if you need to keep the array contents sorted.
Dec 3 '06 #4

DeMan
100+
P: 1,806
You might think this as cheating (and it may not necessarily be very efficient) but:

Java is good at standarising things, and one of the the java has standardised is the idea of a container. I assume, for some reason, you have to use an array, however there is a data type (under the 'container' banner in java) which does exactly what you want....the set. Even though you are using an array, you can exploit the set to get rid of duplicates for you (assuming you include java.util). The container class has and addAll method which includes (or used to include) a variant that accepts an array as input (the array has to be of a type that extends object, which int doesn't really, although in later versions of data this should be cast (without you seeing) into the Integer type <which does extend object>. It also (being a container class) has a method toArray which returns all the elements in an array Thus you can (provided you don't want to keep the empty elements in the array, that is...you don't want to add elements to the array after removing duplicatates):
Expand|Select|Wrap|Line Numbers
  1. Set mySet = new HashSet();
  2. mySet.addAll(inputArray);
  3. inputArray=mySet.toArray();
  4. /*if you need order to your array you can use the following as well */
  5. inputArray=Arrays.sort(inputArray);  //I've not used java for a while so this may be slightly wrong
  6.  
inputArray now has no duplicates (and no extra empty spaces either, so the size has changed, therefore be careful how you iterate through it (make sure you use the new size).

If you don't need to use an array at all, and never want duplicates in your structure, consider using a set (although sets have no real order so they are not ideal for data that needs to be in a certain order).

HOPE THIS HELPS!!
Dec 4 '06 #5

P: 13
Thanks alot for the info but I'm just a beginner so all this is going over my head.

The method I'm trying to write is a basic one. I would also say now I want to make a copy of array of integers. When a copy is made, then I would remove duplicates.

Would method work conceptualy?

Expand|Select|Wrap|Line Numbers
  1. public static String [] remove(String [] arr, int index){
  2.         if(index < 0 || index >= arr.length){
  3.             return null;
  4.         }
  5.         String [] arr2 = new String[arr.length - 1];
  6.         for(int i = 0, j = 0; i < arr.length && j < arr2.length; ++i){
  7.             if(i != index){
  8.                 arr2[j++] = arr[i];
  9.             }
  10.         }
  11.         return arr2;
  12.     }
  13.  
Dec 5 '06 #6

DeMan
100+
P: 1,806
Your method appears to take one element out per call which could be inefficient....

java.util (i think) includes the Arrays methods (which are static so they don't behave quite like normal so pay attention)......

Suppose you have arrays called temp[] and temp2[] (where temp2 is either unitialised or has same size as temp),
we can sort it by calling temp2[]=Arrays.sort(temp);

then we can count how many elements are duplicated .....
Expand|Select|Wrap|Line Numbers
  1. int duplicates=0;
  2. for(int i=1; i<temp2.length; i++) //might be size not length, I always forget.....
  3. {
  4.   if(temp2[i]==temp2[i-1]) //from memory java arrays, like c's start from 0, if not change the 1 to a 2 in the loop above
  5.   {
  6.     duplicates ++;
  7.   }
  8. }
  9.  
duplicates now stores how many values in our array are duplicated, so we can start copying arrays:

Expand|Select|Wrap|Line Numbers
  1. int[] temp3=new int[temp2.length-duplicates];
  2.  
  3. int new_count=0;
  4. temp3[0]=temp2[0];
  5. for(int i=1; i<temp2.length; i++) //again modify if arrays start at 1
  6. {
  7.   if(temp2[i]!=temp3[new_count])
  8.   {
  9.     temp3[new_count+1]=temp2[i];
  10.     new_count++;
  11.   }
  12. }
  13.  
This is not very efficient (and if you have the choice, look up java.util on the net and use a datastructure from it). Java has so many data structures already prepared for you that you can literally pick a data structure for any purpose you can imagine (and they tend to be sim[ple to use because they tend to have the same accessor methods)
Dec 6 '06 #7

P: 32
the problem with using java.util is if this is related to an assignment, the teacher will most likely check to make sure they aren't using libraries. I can tell you in my class we are explicitly forbidden from using libraries that are outside java.lang unless otherwise noted.
Dec 7 '06 #8

P: 13
DeMan -

The code you wrote if I wanted to compile and use it would it work for my problem?

kotoro -

I know for sure that I can use java.util

I want to make a method called printArray() so I can print out the results so would this work?

Expand|Select|Wrap|Line Numbers
  1. public static void printArray(int[] a) {
  2.         for (int i = 0; i < a.length; i++) {
  3.             System.out.println(a[i]);
  4.         }
  5.     }
Dec 7 '06 #9

P: 1
DeMan -

The code you wrote if I wanted to compile and use it would it work for my problem?

kotoro -

I know for sure that I can use java.util

I want to make a method called printArray() so I can print out the results so would this work?

Expand|Select|Wrap|Line Numbers
  1. public static void printArray(int[] a) {
  2.         for (int i = 0; i < a.length; i++) {
  3.             System.out.println(a[i]);
  4.         }
  5.     }

Your code would work but it would print out all of elements in a verticle line, i.e.:
4
5
6
...

You would probably want to do this, to get them all into a single row.
Expand|Select|Wrap|Line Numbers
  1. public static void printArray(int[] a) 
  2. {
  3.      for(int i = 0; i <a.length; i++) 
  4.      {
  5.            System.out.print(a[i] + " ");    // Doesn't leave the line, only adds a space for each new element.
  6.      }
  7.      System.out.println();     // Returns to the next line.
  8. }
Feb 15 '08 #10

Post your reply

Sign in to post your reply or Sign up for a free account.