Re: How to remove duplicate values in an array.
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