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

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

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

 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 ()) и выполните итерации по списку, проверяя, равен ли текущий элемент предыдущему элементу, если он есть, удалите его.

Answer 2

Ниже приведен код для удаления дублирующихся элементов из списка без изменения порядка списка, без использования временного списка и без использования каких-либо установленных переменных. Этот код экономит память и повышает производительность.

Это универсальный метод, который работает с любым списком.

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

    public List<?> removeDuplicate(List<?> listWithDuplicates) {
    int[] intArray = new int[listWithDuplicates.size()];
    int dupCount = 1;
    int arrayIndex = 0;
    int prevListIndex = 0; // to save previous listIndex value from intArray
    int listIndex;

    for (int i = 0; i < listWithDuplicates.size(); i++) {
        for (int j = i + 1; j < listWithDuplicates.size(); j++) {
            if (listWithDuplicates.get(j).equals(listWithDuplicates.get(i)))
                dupCount++;

            if (dupCount == 2) {
                intArray[arrayIndex] = j; // Saving duplicate indexes to an array
                arrayIndex++;
                dupCount = 1;
            }
        }
    }

    Arrays.sort(intArray);

    for (int k = intArray.length - 1; k >= 0; k--) {
        listIndex = intArray[k];
        if (listIndex != 0 && prevListIndex != listIndex){
            listWithDuplicates.remove(listIndex);
            prevListIndex = listIndex;
        }
    }
    return listWithDuplicates;
}

Answer 3

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;

}

Answer 4

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

RemoveDuplicacy.java

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

Пример: Предположим, что при использовании массива типа класса:

ArrayList<User> usersList = new ArrayList<User>();
        usersList.clear();

        User user = new User();
        user.setName("A");
        user.setId("1"); // duplicate
        usersList.add(user);

        user = new User();
        user.setName("A");
        user.setId("1"); // duplicate
        usersList.add(user);

        user = new User();
        user.setName("AB");
        user.setId("2"); // duplicate
        usersList.add(user);

        user = new User();
        user.setName("C");
        user.setId("4");
        usersList.add(user);

        user = new User();
        user.setName("A");
        user.setId("1"); // duplicate
        usersList.add(user);

        user = new User();
        user.setName("A");
        user.setId("2"); // duplicate
        usersList.add(user);


}

Класс, для которого является основой для массива, использованного выше: Класс пользователя

class User {
    private String name;
    private String id;

    /**
     * @param name
     *            the name to set
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * @return the name
     */
    public String getName() {
        return name;
    }

    /**
     * @param id
     *            the id to set
     */
    public void setId(String id) {
        this.id = id;
    }

    /**
     * @return the id
     */
    public String getId() {
        return id;
    }

}

Теперь в Java есть два переопределенных метода класса Object (parent), которые могут помочь в этом способе лучше служить нашей цели. Это:

@Override
    public int hashCode() {

        final int prime = 31;
        int result = 1;
        result = prime * result + ((id == null) ? 0 : id.hashCode());
        return result;

    }

    @Override
    public boolean equals(Object obj) {

        if (this == obj)
            return true;

        if (obj == null)
            return false;

        if (getClass() != obj.getClass())
            return false;

        User other = (User) obj;

        if (id == null) {
            if (other.id != null)
                return false;

        } else if (!id.equals(other.id))
            return false;

        return true;

    }

Вы должны переопределить эти методы в классе User

Вот полный код:

https://gist.github.com/4584310

Дайте мне знать, если у вас есть какие-либо вопросы.

Answer 5

Вы можете добавить список в HashSet, а затем снова преобразовать этот хэш-набор в список для удаления дубликатов.

public static int removeDuplicates(List<String> duplicateList){
    List<String> correctedList = new ArrayList<String>();
    Set<String> a = new HashSet<String>();
    a.addAll(duplicateList);
    correctedList.addAll(a);
    return (duplicateList.size()-correctedList.size());
}

здесь будет возвращено количество дубликатов. Вы также можете использовать correctList со всеми уникальными значениями

Answer 6

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

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

Answer 7

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

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

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

Answer 8

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

Например:

{"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' ... упс.

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

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

Answer 9

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

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

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

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

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

Answer 10

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(Integer key, List<Foo> value) метод. Если вы хотите изменить исходный список (возможно, не очень хорошая идея, но что угодно), вместо этого:

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

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

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