массив - эффективность и общий подход к вопросу

Question

Редактировать ** После долгой игры с моим кодом я написал несколько версий, одна из которых - то, что я искал.

Answer 1

Если вы можете пожертвовать немного больше места для оптимизации по времени.

По сути, просто создайте другой массив missing и заполните его тем, чего не хватает, пройдя массив helper.

Изменено ваше оригинальное решение.

  int input  [] = {5,6,0,3,0,2,1};
  int output [] = new int[input.length];  
  boolean [] helper  = new boolean[input.length];

  for(int i = 0; i <input.length; i++)
  {
      if(input[i] != 0)
          helper[i] = true;
  }

  int missing [] = new int[input.length];
  int missingCount = 0;

   for(int j = 0; j < helper.length; j++)
  {
      if(!helper[j]){ 
         missing[missingCount++] = j;

      }
  }
  missingCount = 0;
  for(int j = 0; j < input.length; j++){
      if(input[j]==0){
           input[j]=missing[missingCount++];
      }
  }

Answer 2

Ниже код может найти недостающий элемент и добавить его обратно в сложности O (n):

notFound - будет хранить индекс или местоположение входной массив, имеющий номер с нулем

numberDetails - содержит сведения о числах, независимо от того, присутствует ли он во входном массиве или нет (true или false)

Пример : input [3] = false означает, что 4 (3 + 1) отсутствует во входном массиве, input [4] = true означает, что 5 (4 + 1) присутствует во входном массиве

        int input[] = { 5, 6, 0, 3, 0, 2, 1 };
        int notFound[] = new int[input.length];
        boolean[] numberDetails = new boolean[input.length];
        int notFoundIndex=0;
        for(int i=0;i<input.length;i++) {
            if(input[i]==0) {
                notFound[notFoundIndex++]=i;
            }
            else {
                numberDetails[input[i]-1]=true;
            }

        }
        notFoundIndex=0;
        for(int j=0;j<numberDetails.length;j++) {
            if(!numberDetails[j]) {
                input[notFound[notFoundIndex++]] = j+1;
            }   
        }
        System.out.println(Arrays.toString(input));

Answer 3

Я бы сделал следующее:

1. Создание помощника Set со всеми числами от 1 до 100 - O (n) во времени и пространстве
2. Создание (изначально) пусто Set для записи индексов с 0s - O (1)
3. Go по массиву - O (n):
   1. Если значение равно 0, добавьте индекс для набора индексов
   2. Если значение не равно 0, удалите его из вспомогательного набора
4. Go поверх вспомогательного набора и назначьте оставшиеся значения к индексам, сохраненным в наборе индексов - O (m), где m <= n </li>

В целом - решение O (n) во времени и пространстве.

In java:

int[] numbers = /* the array with missing numbers */
Set<Integer> allNumbers = IntStream.rangeClosed(1, 100).boxed().Collect(Collectors.toSet()); 
Set<Ineteger> missingIndexes = new HashSet<>();

for (int i = 0; i < numbers.length; ++i) {
    if (numbers[i] == 0) {
        missingIndexes.add(i);
    } else {
        allNumbers.remove(i);
    }
}

Iterator<Integer> numberIter = allNumbers.iterator();
Iterator<Integer> indexIter = missingIndexes.iterator();

while (numberIter.hasNext() && indexIter.hasNext()) {
    numbers[indexIter.next()] = numberIter.next();
}