Java - Удаляющие дубликаты в ArrayList

Использование набора - лучший вариант (как предлагали другие).

Если вы хотите сравнить все элементы в списке друг с другом, вам следует немного изменить циклы for:

for(int i = 0; i < max; i++)
    for(int j = i+1; j < max; j++)

Таким образом, вы не сравниваете каждый элемент только один раз, а не дважды. Это потому, что второй цикл начинается со следующего элемента по сравнению с первым циклом.

Также при удалении из списка при итерации по ним (даже если вы используете цикл for вместо итератора), имейте в виду, что вы уменьшаете размер списка. Распространенное решение - сохранить другой список элементов, которые вы хотите удалить, а затем, после того как вы закончите решать, какие из них удалить, вы удалите их из исходного списка.

Вы можете заменить дубликат пустой строкой *, сохранив таким образом индексацию. Затем после того, как вы закончите, вы можете вырезать пустые строки.

* Но только если пустая строка недопустима в вашей реализации.

Предполагая, что вы не можете использовать Set, как вы сказали, самый простой способ решить проблему - использовать временный список, а не пытаться удалить дубликаты на месте:

public class Duplicates {

    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("one");
        list.add("one");
        list.add("two");
        list.add("three");
        list.add("three");
        list.add("three");

        System.out.println("Prior to removal: " +list);
        System.out.println("There were " + removeDuplicates(list) + " duplicates.");
        System.out.println("After removal: " + list);
    }

    public static int removeDuplicates(List<String> list) {
        int removed = 0;
        List<String> temp = new ArrayList<String>();

        for(String s : list) {
            if(!temp.contains(s)) {
                temp.add(s);
            } else {
                //if the string is already in the list, then ignore it and increment the removed counter
                removed++;
            }
        }

        //put the contents of temp back in the main list
        list.clear();
        list.addAll(temp);

        return removed;
    }

}

Почему бы не использовать такую ​​коллекцию, как Set (и такую ​​реализацию, как HashSet ), которая естественным образом предотвращает дублирование?

public <Foo> Entry<Integer,List<Foo>> uniqueElementList(List<Foo> listWithPossibleDuplicates) {
  List<Foo> result = new ArrayList<Foo>();//...might want to pre-size here, if you have reliable info about the number of dupes
  Set<Foo> found = new HashSet<Foo>(); //...again with the pre-sizing
  for (Foo f : listWithPossibleDuplicates) if (found.add(f)) result.add(f);
  return entryFactory(listWithPossibleDuplicates.size()-found.size(), result);
}

, а затем некоторый метод entryFactory (Целочисленный ключ, значение List ) . Если вы хотите изменить исходный список (возможно, не очень хорошая идея, но что угодно) вместо этого:

public <Foo> int removeDuplicates(List<Foo> listWithPossibleDuplicates) {
  int original = listWithPossibleDuplicates.size();
  Iterator<Foo> iter = listWithPossibleDuplicates.iterator();
  Set<Foo> found = new HashSet<Foo>();
  while (iter.hasNext()) if (!found.add(iter.next())) iter.remove();
  return original - found.size();
}

для вашего конкретного случая с использованием строк, вам может потребоваться иметь дело с некоторыми дополнительными ограничениями равенства (например, одинаковые или разные версии в верхнем и нижнем регистре?).

РЕДАКТИРОВАТЬ: ах, это домашнее задание. Найдите Iterator / Iterable в структуре Java Collections, а также Set, и посмотрите, не пришли ли вы к тому же выводу, что я предложил. Часть дженериков - просто подливка.

Проблема, которую вы видите в своем коде, заключается в том, что вы удаляете запись во время итерации, что делает недействительным местоположение итерации.

Например:

{"a", "b", "c", "b", "b", "d"} 
       i         j  

Теперь вы удаляете строки [j].

{"a", "b", "c", "b", "d"} 
       i         j  

Внутренний цикл заканчивается, и j увеличивается на единицу.

{"a", "b", "c", "b", "d"} 
       i              j

Обнаружен только один дубликат 'b' ... ой.

Лучшая практика в этих случаях - сохранить местоположения, которые необходимо удалить, и удалить их после того, как вы закончите итерацию по arrayylist. (Один бонус, вызов strings.size () может быть оптимизирован вне циклов вами или компилятором)

Совет, вы можете начать итерацию с j с i + 1, вы уже проверили 0 - i!

Чтобы прояснить мой комментарий к ответу Мэтта Б., если вы действительно хотите подсчитать количество удаленных дубликатов, используйте этот код:

List<String> list = new ArrayList<String>();

// list gets populated from user input...

Set<String> set = new HashSet<String>(list);
int numDuplicates = list.size() - set.size();

Я пытался использовать вложенные циклы для этого, но у меня возникли проблемы, потому что когда записи удаляются , индексирование ArrayList изменяется , и все работает не так, как должно

Почему бы вам просто не уменьшать счетчик каждый раз, когда вы удаляете запись.

Когда вы удаляете запись, элементы тоже перемещаются:

ej:

String [] a = {"a","a","b","c" }

позиции:

a[0] = "a";
a[1] = "a";    
a[2] = "b";
a[3] = "c";

После того, как вы удалите первую букву «а», индексы будут:

a[0] = "a";
a[1] = "b";
a[2] = "c";

Итак, вы должны принять это во внимание и уменьшите значение j ( j - ), чтобы избежать «перепрыгивания» значения.

Смотрите этот снимок экрана:

Внутренний цикл for недействителен. Если вы удалите элемент, вы не сможете увеличить j , поскольку j теперь указывает на элемент после того, который вы удалили, и вам нужно будет его проверить.

Другими словами, вы должны использовать цикл while вместо цикла for и увеличивать только j , если элементы в i и j не совпадают. Если они соответствуют , удалите элемент в j . size () уменьшится на 1, и j теперь будет указывать на следующий элемент, поэтому нет необходимости увеличивать j .

Кроме того, нет причин проверять все элементы во внутреннем цикле, только те, которые следуют за i , поскольку дубликаты до i уже удалены предыдущими итерациями.

public ArrayList removeDuplicates(ArrayList <String> inArray)
{
    ArrayList <String> outArray = new ArrayList();
    boolean doAdd = true;
    for (int i = 0; i < inArray.size(); i++)
    {
        String testString = inArray.get(i);
        for (int j = 0; j < inArray.size(); j++)
        {
            if (i == j)
            {
                break;
            }
            else if (inArray.get(j).equals(testString))
            {
                doAdd = false;
                break;
            }

        }
        if (doAdd)
        {
            outArray.add(testString);
        }
        else
        {
            doAdd = true;
        }

    }
    return outArray;

}

public Collection removeDuplicates(Collection c) {
// Returns a new collection with duplicates removed from passed collection.
    Collection result = new ArrayList();

    for(Object o : c) {
        if (!result.contains(o)) {
            result.add(o);
        }
    }

    return result;
}

или

public void removeDuplicates(List l) {
// Removes duplicates in place from an existing list
    Object last = null;
    Collections.sort(l);

    Iterator i = l.iterator();
    while(i.hasNext()) {
        Object o = i.next();
        if (o.equals(last)) {
            i.remove();
        } else {
            last = o;
        }
    }
}

Оба не проверены.

Вы могли бы попробовать этот один лайнер для снятия копии строки с сохранением порядка.

List<String> list;
List<String> dedupped = new ArrayList<String>(new LinkedHashSet<String>(list));

Этот подход также амортизируется O(n) вместо O(n^2)

Вы можете использовать вложенные циклы без проблем:

public static int removeDuplicates(ArrayList<String> strings) {

    int size = strings.size();
    int duplicates = 0;

    // not using a method in the check also speeds up the execution
    // also i must be less that size-1 so that j doesn't
    // throw IndexOutOfBoundsException
    for (int i = 0; i < size - 1; i++) {
        // start from the next item after strings[i]
        // since the ones before are checked
        for (int j = i + 1; j < size; j++) {
            // no need for if ( i == j ) here
            if (!strings.get(j).equals(strings.get(i)))
                continue;
            duplicates++;
            strings.remove(j);
            // decrease j because the array got re-indexed
            j--;
            // decrease the size of the array
            size--;
        } // for j
    } // for i

    return duplicates;

}

Использование множества - лучший вариант для удаления дубликатов:

Если у вас есть список массивов, вы можете удалить дубликаты и сохранить свойства списка массивов:

 List<String> strings = new ArrayList<String>();
 //populate the array
 ...
 List<String> dedupped = new ArrayList<String>(new HashSet<String>(strings));
 int numdups = strings.size() - dedupped.size();

Если вы не можете использовать множество, отсортируйте массив (Collections.sort()) и итерируйте список, проверяя, равен ли текущий элемент предыдущему, если да, удалите его.