Java - удаление дубликатов в ArrayList

Question

Я работаю над программой, которая использует ArrayList для хранения Strings. Программа предлагает пользователю меню и позволяет пользователю выбрать операцию для выполнения. Такими операциями являются добавление строк в список, печать записей и т. Д. Я хочу создать метод с именем removeDuplicates(). Этот метод будет искать ArrayList и удалять все дублированные значения. Я хочу оставить один экземпляр дублирующихся значений в списке. Я также хочу, чтобы этот метод возвращал общее количество удаленных дубликатов.

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

Вот некоторый псевдокод:

начать с первой записи; проверьте каждую последующую запись в списке и посмотрите, соответствует ли она первой записи; удалить каждую последующую запись в списке, соответствующую первой записи;

после изучения всех записей переходите ко второй записи; проверьте каждую запись в списке и посмотрите, соответствует ли она второй записи; удалить каждую запись в списке, которая соответствует второй записи;

повторить для записи в списке

Вот код, который у меня есть:

public int removeDuplicates()
{
  int duplicates = 0;

  for ( int i = 0; i < strings.size(); i++ )
  {
     for ( int j = 0; j < strings.size(); j++ )
     {
        if ( i == j )
        {
          // i & j refer to same entry so do nothing
        }

        else if ( strings.get( j ).equals( strings.get( i ) ) )
        {
           strings.remove( j );
           duplicates++;
        }
     }
 }

   return duplicates;
}

ОБНОВЛЕНИЕ : Похоже, что Уилл ищет решение домашней работы, которое включает разработку алгоритма удаления дубликатов, а не прагматическое решение с использованием наборов. Смотрите его комментарий:

Спасибо за предложения. Это часть задания, и я считаю, что учитель намеревался, чтобы решение не включало наборы. Другими словами, я должен предложить решение, которое будет искать и удалять дубликаты без реализации HashSet. Учитель предложил использовать вложенные циклы, что я и пытаюсь сделать, но у меня были некоторые проблемы с индексированием ArrayList после удаления некоторых записей.

Answer 1

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

Answer 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;

}

Answer 3

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

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

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

Answer 4

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

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();

Answer 5

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

lst.add("one");
lst.add("one");
lst.add("two");
lst.add("three");
lst.add("three");
lst.add("three");
Set se =new HashSet(lst);
lst.clear();
lst = new ArrayList<String>(se);
for (Object ls : lst){
    System.out.println("Resulting output---------" + ls);   
}

Answer 6

Я пытался использовать вложенные циклы для достижения этой цели, но у меня возникали проблемы, потому что, когда записи удаляются , индексация 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--), чтобы избежать "перепрыгивания" через значение.

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

Answer 7

Очень простой способ удалить дубликаты строк из списка пользователей

ArrayList al = new ArrayList();
// add elements to al, including duplicates
HashSet hs = new HashSet();
hs.addAll(al);
al.clear();
al.addAll(hs);

Answer 8

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;
        }
    }
}

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

Answer 9

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

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;
    }

}

Answer 10

Вы могли бы сделать что-то вроде этого, но из того, что люди ответили выше, есть одна альтернатива, но вот другая.

for (int i = 0; i < strings.size(); i++) {
    for (int j = j + 1; j > strings.size(); j++) {
      if(strings.get(i) == strings.get(j)) {
            strings.remove(j);
            j--;
       }`
    }
  }

return strings;