Удалить дубликаты из массива без использования Set и библиотечных методов

Рейтинг: -5Ответов: 1Опубликовано: 06.03.2023
public static void printWordsRev(String s) {

}

Ниже приведён пример входных и выходных данных.

Входные данные: "money honey happy money honey money happy money happy".

Выходные данные: "money honey happy".

Можно использовать только ArrayList, без Set.

Ответы

▲ 2

Если можно использовать "библиотечные" методы интерфейса List, то для этой задачи можно предложить несколько решений. Также стоит сделать общие методы для получения списка слов из строки и печати списка строк.

  1. Вложенные циклы с удалением всех дубликатов после данного слова
    Для каждого i-го слова проверяем все оставшиеся слова и удаляем дубликаты:```
private static List<String> getWords(String str) {
    return new ArrayList<>(Arrays.asList(str.split("\\s+")));
}

private static void print(List<String> words) {
    System.out.println(String.join(" ", words));
}

public static void printWordsRevFor1(String s) {
    List<String> words = getWords(s);
    for (int i = 0; i < words.size(); i++) {
        String w = words.get(i);
        for (int j = i + 1; j < words.size(); j++) {
            if (w.equals(words.get(j))) {
                words.remove(j--); // коррекция индекса после удаления
            }
        }
    }
    print(words);    
}

1a. Удаление дубликатов в конце списка

public static void printWordsRev1a(String s) {
    List<String> words = getWords(s);
    for (int i = 0; i < words.size(); i++) {
        String w = words.get(i);
        for (int j = words.size() - 1; j > i; j--) {
            if (w.equals(words.get(j))) {
                words.remove(j);
            }
        }
    }
    
    print(words);
}
  1. Установка дубликатов в null с последующим удалением при помощи List::removeIf
public static void printWordsRev2(String s) {
    List<String> words = getWords(s);
    for (int i = 0, n = words.size(); i < n; i++) {
        String w = words.get(i);
        if (w == null) continue; // пропустить уже найденный дубликат
        for (int j = i + 1; j < n; j++) {
            if (w.equals(words.get(j))) {
                words.set(j, null);
            }
        }
    }
    words.removeIf(w -> null == w);
    
    print(words);
}
  1. Поиск дубликатов с конца массива с помощью List::lastIndexOf
public static void printWordsRev3(String s) {
    List<String> words = getWords(s);
    
    for (int i = 0; i < words.size(); i++) {
        String w = words.get(i);
        int j;
        while ((j = words.lastIndexOf(w)) != i) {
            words.remove(j);
        }
    }
    
    print(words);
}
  1. "Читерское" использование List::stream:
public static void printWordsRev4(String s) {
    print(getWords(s).stream().distinct().toList());
}

Ещё пара способов:
5. Удаление дубликатов при помощи List::subList + List.removeIf:
Известно, что List::subList не создаёт новый список, а является представлением текущего списка, соответственно, изменения в подсписке, полученном таким образом, будут применяться и к начальному списку.

public static void printWordsRev5(String s) {
    List<String> words = getWords(s);
    for (int i = 0; i < words.size(); i++) {
        String w = words.get(i);
        words.subList(i + 1, words.size()).removeIf(w::equals);
    }
    
    print(words);
}
  1. Использование итератора ListIterator + List::indexOf для удаления в конце списка
public static void printWordsRev6(String s) {
    //print(getWords(s).stream().distinct().toList());
    List<String> words = getWords(s);

    // итератор списка с конца
    ListIterator<String> it = words.listIterator(words.size());
    
    while (it.hasPrevious()) {
        String tail = it.previous();
        int ix = it.previousIndex() + 1;
        if (ix > words.indexOf(tail)) {
            it.remove();
        }
    }

    print(words);
}