Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.help > #2802

Re: How to remove duplicate values in an array.

Show key headers only | View raw

On 13/10/13 06:18, miss.smileyfish@gmail.com wrote:
> I have some code to build an object elementData that stores a list of ints in an array and also keeps track of a boolean unique that determines if duplicates are allowed in a list. I have written a small method to search out duplicates and remove them, but for some reason it is not working. I am not sure if the problem is with the method itself or the placement of the call to the removeDuplicates method.
>
>     // post: places the value in the correct place based on ascending order
>     public void add(int value) {
>        size++;
>        if (size == 1) {
>           elementData[0] = value;
(I'm not sure you need this branch.  binarySearch would have to quickly 
yield -1, position would take the value 0, the shifting loop would have 
zero iterations, and the value would be assigned to position zero.)
>        } else {
>           int position =  Arrays.binarySearch(elementData, 0, size - 1, value);
>           if (position < 0 ) {
>              position = (-position) - 1;
>           }
>           for (int i = size - 1; i > position; i--) {
>              elementData[i] = elementData[i - 1];
>           }
>           elementData[position] = value;
>           if (unique) {
>              removeDuplicates();
>           }

You're evidently relying on the sequence being sorted, and ensuring it 
too - so your removeDuplicates could be limited to looking for them only 
where the insertion just took place.  Better still, detect a 
non-negative from binarySearch, and don't bother inserting.

>        }
>     }
>        
>     //post: removes any duplicate values from the list
>     private void removeDuplicates() {
>        for(int i = size - 1; i < 0; i--) {

Surely, i > 0?

>           if (elementData[i] == elementData[i - 1]){
>              remove(i);
>           }
>        }
>     }
>     // pre : 0 <= index < size() (throws IndexOutOfBoundsException if not)
>     // post: removes value at the given index, shifting subsequent values left
>     public void remove(int index) {
>        checkIndex(index);
>        for (int i = index; i < size - 1; i++) {
>           elementData[i] = elementData[i + 1];
>        }
>        size--;
>     }


Do you need the result to be sorted, or are you just using that to help 
remove duplicates?  If it's incidental, you could just add values to a 
HashSet<Integer>.

If sorting is important, but you want to keep duplicates, you could use 
a TreeMap:

   SortedMap<Integer, Integer> map = new TreeMap<>();

   void add(int value) {
     Integer count = map.get(value);
     if (count == null) count = 0;
     count++;
     map.put(value, count);
   }

To sort but avoid duplicates:

   SortedSet<Integer> set = Collections.newSetFromMap(new TreeMap<Integer, Boolean>());

   void add(int value) {
     set.add(value);
   }

Or use unsorted collections, and sort after.


-- 
ss at comp dot lancs dot ac dot uk

Back to comp.lang.java.help | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How to remove duplicate values in an array. miss.smileyfish@gmail.com - 2013-10-12 22:18 -0700
  Re: How to remove duplicate values in an array. Steven Simpson <ss@domain.invalid> - 2013-10-13 10:00 +0100
  Re: How to remove duplicate values in an array. Joerg Meier <joergmmeier@arcor.de> - 2013-10-13 12:09 +0200
  Re: How to remove duplicate values in an array. Roedy Green <see_website@mindprod.com.invalid> - 2013-10-21 20:34 -0700
    Re: How to remove duplicate values in an array. Lew <lewbloch@gmail.com> - 2013-10-23 15:58 -0700

csiph-web