Подтвердить что ты не робот

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

Я работаю над программой, которая использует 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;
}

UPDATE. Похоже, что Уилл ищет домашнее решение, которое предполагает разработку алгоритма для удаления дубликатов, а не прагматичное решение с использованием Sets. См. Его комментарий:

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ответ 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;

}

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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

ej:

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

позиции:

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

После того, как вы удалите первый "a", индексы:

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

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

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

its working

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

Ответ 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;
    }

}

Ответ 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;

Ответ 11

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

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

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

Ответ 12

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

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

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

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

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

Ответ 13

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;

}

Ответ 14

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

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

Ответ 15

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

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

EDIT: ах, это домашнее задание. Посмотрите Iterator/Iterable в структуре Java Collections, а также Set, и посмотрите, не пришли ли вы к тому же выводу, который я предлагал. Часть дженериков - просто соус.

Ответ 16

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

Например:

{"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" обнаружен... oops.

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

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

Ответ 17

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

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

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

Ответ 18

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

RemoveDuplicacy.java

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

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

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

@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

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

Ответ 19

Вы можете добавить список в 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());
}

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

Ответ 20

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

Это общий метод, который работает с любым списком.

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

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