Блог

Я хочу заменить повторяющиеся целые числа в ArrayList размера n отсутствующими целыми числами. Например:

 import java.util.ArrayList;

public class Main {

  public static void main(String[] args) {

    ArrayList<Integer> myNumbers = new ArrayList<Integer>();
    myNumbers.add(1);
    myNumbers.add(2);
    myNumbers.add(1);
    myNumbers.add(3);
    myNumbers.add(1);
   
  }
}

 

Arraylist содержит 5 элементов, поэтому он должен содержать числа 1 ,2 ,3 ,4, 5 ( не в определенном порядке).
(если размер был 99, должны быть числа от 1 до 99 без дубликатов).

он должен перейти от [1,2,1,3,1] к [1,2,4,3,5] или [1,2,5,3,4] . Он должен работать для любого размера, и может быть несколько дубликатов.

На данный момент я могу избавиться от дубликатов только с помощью set, но я понятия не имею, как заменить их недостающими элементами.

1. Сначала найдите недостающие значения
2. Выполните итерацию по вашему списку и проверьте, является ли текущее значение дубликатом. Если true, замените одним из отсутствующих значений

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

 import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Test {

    public static void main(String[] args) {
        List<Integer> myNumbers = new ArrayList<>();
        myNumbers.add(1);
        myNumbers.add(2);
        myNumbers.add(1);
        myNumbers.add(3);
        myNumbers.add(1);
        System.out.println("original: "   myNumbers);
        List<Integer> missing = IntStream.rangeClosed(1,myNumbers.size())
                .filter(i -> !myNumbers.contains(i))
                .boxed().collect(Collectors.toList());
        System.out.println("missing: "   missing);

        Set<Integer> unique = new HashSet<>();
        Iterator<Integer> misIterator = missing.iterator();
        for(int i = 0; i < myNumbers.size(); i  ){
            if(!unique.add(myNumbers.get(i))){
                myNumbers.set(i, misIterator.next());
            }
        }
        System.out.println("modified"   myNumbers);
    }
}
 

Это мое понимание вопроса / постановки проблемы:

• Ваш ввод представляет собой список возможных дублированных чисел 1 — n, где n никогда не превышает размер списка.
• Первый экземпляр (не повторяющийся) числа при итерации списка должен быть оставлен с его текущим индексом.
• Каждый последующий дубликат числа, найденный при повторении списка, должен быть заменен числом из «отсутствующего набора».
• «Отсутствующий набор» содержит все числа 1 — n, где n — размер списка с удаленным существующим набором (из входного списка).
• Список конечных результатов должен содержать все числа 1 — listSize без дубликатов, а первый экземпляр любых чисел (при итерации с начала списка) остается с тем же индексом, что и входной список.

Если приведенные выше утверждения звучат правильно, вот один из способов сделать это (хотя, вероятно, есть более оптимизированный способ сделать это):

 import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ReplaceDuplicateIntegersRunner {
    private static ArrayList<Integer> sampleIntegerList = new ArrayList<>();

    public static void main(String[] args) {
        addRandomIntegersToList(3,7);
        System.out.println("List Before: "   sampleIntegerList);
        replaceDuplicatesWithContinuedCount();
        System.out.println("List After: "   sampleIntegerList);

    }

    public static void addRandomIntegersToList(Integer maxValue, Integer numOfIntegers) {
        Random randomGen = new Random();
        for (int num = 0; num < numOfIntegers; num  ) {
            sampleIntegerList.add(1   randomGen.nextInt(maxValue));
        }
    }

    public static void replaceDuplicatesWithContinuedCount() {
        // generate a set of integers 1 - length of sampleIntegerList
        Set<Integer> integerSetToAdd = IntStream.rangeClosed(1, sampleIntegerList.size())
                .boxed().collect(Collectors.toSet());
        // remove the integers which already exist in the target sample list
        integerSetToAdd.removeAll(new HashSet<>(sampleIntegerList));
        ArrayList<Integer> integersToReplaceDuplicates = new ArrayList<>();
        integersToReplaceDuplicates.addAll(integerSetToAdd);
        int indexOfIntegersToAdd = 0;
        HashSet<Integer> duplicatesInList = new HashSet<>();
        for (int index = 0; index < sampleIntegerList.size(); index  ) {
            // if our duplicate set doesn't already have this number, we don't have a duplicate, add it to the set
            // and continue on
            Integer integerAtIndex = sampleIntegerList.get(index);
            if (duplicatesInList.contains(integerAtIndex) == false) {
                duplicatesInList.add(integerAtIndex);
            } else {
                // otherwise we've found a duplicate and need to replace it with the next one to replace
                sampleIntegerList.set(index, integersToReplaceDuplicates.get(indexOfIntegersToAdd));
                indexOfIntegersToAdd  ;
            }
        }
    }
}
 

Некоторые примеры выходных данных с переданными параметрами in сверху:

Список перед: [3, 2, 3, 3, 1, 1, 1] Список после: [3, 2, 4, 5, 1, 6, 7]

Список перед: [2, 3, 2, 2, 3, 2, 1] Список после: [2, 3, 4, 5, 6, 7, 1]

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

 List<Integer> list = IntStream
        // from 1 to 5 inclusive
        .rangeClosed(1, 5)
        // Stream<Integer>
        .boxed()
        .collect(Collectors.toList());

// random order
Collections.shuffle(list);

System.out.println(list); // [2, 4, 3, 1, 5]