Самый эффективный способ удалить последовательные элементы из массива? Java - PullRequest
Новая
       7

Самый эффективный способ удалить последовательные элементы из массива? Java

3 голосов
/ 21 февраля 2020

Я пытаюсь решить эту проблему наиболее эффективным способом.

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

Например, int [] {4,4,7,7,6,6,6,7,4} вернет 3. Когда мы удаляем последовательный 6, массив int становится {4, 4,7,7,7,4} в следующей итерации удаляются последовательные 7, и у нас остается {4,4,4} и т. Д.

int [] {3,4, 4,5,5,3} вернет 0.

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

    public static int getNumberOfRepetitions(int[] arr) {

    int[] arr2 = new int[arr.length];
    int counter= 0;
    int index = 0;

    for (int x= 0;x<arr.length;x++) {
        if (x < arr.length - 2) {
            if (arr[x] == arr[x + 2] && arr[x] == arr[x + 2]) {
                counter++;
                x = x + 2;
                continue;
            }
            arr2[index] = arr[x];
            index++;
        }
        if (x < arr.length - counter * 3) {
            arr = arr2;
            arr2 = new int[arr.length];
            index = 0;
            x = -1;
        }
    }
    return counter;
}

Алгоритм перебирает массив и добавляет элементы во второй массив, если есть последовательные элементы, он добавляет счетчик и пропускает их. На последней итерации arr устанавливается в arr2 и для l oop должен сбрасываться.

Пока я не могу понять, как завершить код, поэтому я получил бесконечное l oop. Я новичок в программировании и буду признателен за любую помощь.

Ответы [ 3 ]

4 голосов
/ 21 февраля 2020

В вашей логике есть несколько ошибок c. Вместо того, чтобы указывать каждый из них, вот новый подход: 

private static int getNumberOfRepetitions(int[] arr) {
    int[] arr2 = new int[arr.length];
    int counter= 0;
    int j = 0;
    for (int i : arr) {
        arr2[j++] = i;
        if (j > 2) {
            if (arr2[j - 1] == arr2[j - 2] && arr2[j - 1] == arr2[j - 3]) {
                counter++;
                j -= 3;
            }
        }
    }
    return counter;
}

Здесь мы добавляем элементы в новый массив один за другим и поддерживаем индекс для этого массива. Когда в новом массиве есть 3 элемента, сравните последние 3. Если они равны, уменьшите индекс ('j') на 3.

3 голосов
/ 21 февраля 2020

Мне сказали, что мой код требует слишком много операций и слишком медленный.

Это правильно, потому что вы действительно можете сделать это, даже не изменяя массив.

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

  1. Инициализация счетчик до 0 и начните итерацию с начала массива.

  2. Найдите следующий (первый) триплет.
    Если ничего не найдено, все готово, поэтому верните счетчик значение. 

          start
        │  end
        │   │
4,4,7,7,6,6,6,7,4

  3. Вы нашли триплет для удаления, поэтому увеличьте счетчик на 1.

  4. Сравните окружающие значения. Сначала сравните значения непосредственно до и после.
    Если они разные, перейдите к шагу 7. 

          start
        │  end
        │   │
4,4,7,7,6,6,6,7,4
      └───────┘ are they equal?

  5. Когда окружающие значения равны, есть две возможности для каскадного триплета, либо дополнительное значение до, либо дополнительное значение после.
    Если дополнительное значение до / после отличается от окружающих значений, перейдите к шагу 7. 

          start                                start
        │  end                               │  end
        │   │                    O R         │   │
4,4,7,7,6,6,6,7,4                        4,7,6,6,6,7,7,4,4
    └─┴───────┘ are they equal?            └───────┴─┘ are they equal?

  6. Развернуть последовательность, которую нужно удалить, и go вернитесь к шагу 3, чтобы повторить каскадный поиск. 

      start                       start
    │        end                │        end
    │         │       O R       │         │
4,4,7,7,6,6,6,7,4             4,7,6,6,6,7,7,4,4

      start                       start
    │        end                │        end
    │         │       O R       │         │
4,4,7,7,6,6,6,7,4             4,7,6,6,6,7,7,4,4
└─┴─────────────┘             └─────────────┴─┘   are they equal?

  7. Теперь нам нужно найти более сложный непересекающийся триплет. 

    12344433255666527
 ││└┴┘││││││││││   simple triplet found (step 2-3)
 │└───┴┘││││││││   surrounding triplet found (step 4-6)
 │      │││└┴┘││   another simple triplet found
 │      │└┴───┘│   surrounding triplet found
 └──────┴──────┘   disjoint triplet found

    Для этого нам нужно отслеживать предыдущую удаленную последовательность. 

      ┌ prevStart
  │    ┌ prevEnd
  │    │ ┌ start
  │    │ │    ┌ end
12344433255666527
 └──────┴──────┘   are they equal?

    Если предыдущий конец находится на 2 позиции перед новым началом, а 3 значения перед, между и после равны, то мы нашли непересекающийся триплет. Разверните последовательность для удаления, включив в нее предыдущую последовательность, текущую последовательность и новый триплет, затем go вернитесь к шагу 3, чтобы повторить каскадный поиск.

  8. Вы уже нашли раздел для удаления и увеличения счетчика соответствующее количество раз, поэтому начиная с позиции end, go возвращайтесь к шагу 2 для поиска следующего триплета.

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

Код удачи. ?

0 голосов
/ 23 февраля 2020

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

Очень легко проверенный JavaScript код (контрпримеры / ошибки приветствуются ): 

// Returns [count, leftmostIndex]
function f(A, i=0, same=1){
  // Base case, end of list
  if (i > A.length - 1)
    return [0, A.length];
  
  // We can remove this block
  if (A[i] == A[i+1] && same == 2){
    let [count, j] = f(A, i + 2, 1);
    return [count + 1, j];
  }
    
  // Same but the count is less than
  // three, keep accumulating
  if (A[i] == A[i+1])
    return f(A, i + 1, same + 1);
  
  // Next element is different,
  // see if the next section has
  // collapsed blocks
  let [count, j] = f(A, i + 1, 1);
  
  // There is no available element
  // to try and accumulate
  if (j > A.length - 1)
    return [count, i];
    
  // The next available element
  // is the same
  if (A[i] == A[j]){
    // We've reached a count of three,
    // remove this block
    if (same == 2){
      return [count + 1, j + 1];

    // Haven't reached a count of
    // three, try one more section
    } else {
      let [count2, j2] = f(A, j + 1, 1);
      if (A[i] == A[j2])
        return [1 + count + count2, j2 + 1];
      else
        return [count + count2, i];
    }
        
  // The next available element is
  // different
  } else {
    return [count, i];
  }
}

var As = [
  [4,4,7,7,6,6,6,7,4],
  [5,7,7,7,8,4,4,5,5,6,6,6,6,6,6,5,4]
];

for (let A of As){
  console.log(JSON.stringify(A));
  console.log(JSON.stringify(A.map((_, i) => i)));
  console.log(JSON.stringify(f(A)));
}
...