Удаление дубликатов из отсортированного массива

Question

Я наткнулся ниже на вопрос интервью и его решение, и мне трудно разобраться, как он работает:

Учитывая отсортированные номера массивов, удалите дубликаты на месте так, чтобы каждыйЭлемент появляется только один раз и возвращает новую длину.Не выделяйте дополнительное пространство для другого массива, вы должны сделать это, изменив входной массив на месте с помощью O (1) дополнительной памяти.

Ниже приведено решение.Может кто-нибудь объяснить мне, как это работает?Я не в состоянии понять приведенный ниже алгоритм, а также, если я раскомментирую строку system.out, тогда она выдает исключение, так как nums[i - 1] работает в блоке if для случая, когда i=0?

  public static int removeDuplicatess(int[] nums) {
    int i = 0;
    for (int n : nums) {
      // System.out.println(nums[i - 1]);
      if (i == 0 || n > nums[i - 1])
        nums[i++] = n;
    }
    return i;
  }

Answer 1

nums[i - 1] работает из-за краткой оценки сложных логических выражений - когда первый член i == 0 истинен, нет необходимости оценивать второй член (в случае логической операции OR между терминами).

А логика алгоритма проста - если текущее значение совпадает с предыдущим - пропустите его, в противном случае запишите его в сжатую начальную часть массива.

Answer 2

Этот метод повторяет все числа в Array.Он начинается с добавления первого числа в Array, поскольку оно не может быть дубликатом, поскольку это первое число.(Для этого и используется i == 0 часть if. Затем он смотрит на один индекс обратно, чтобы увидеть, если n > nums[i - 1]. Единственный способ, которым это будет верно, - это если n не является дубликатом, так каксписок отсортирован. Если это так, то мы добавляем его в Array. Возьмем этот пример:

[0, 1, 1, 3]

На первой итерации:

• n == 0
• i == 0
• i == 0 оценивается как true. 0 добавляется к индексу 0.

Вторая итерация:

• n == 1
• i == 1
• n > nums[i - 1] (1> 0) оценивается как true, 1 добавляется к Array

Третья итерация:

• n == 1
• i == 2
• n > nums[i - 1] (1> 1) оценивается как false, так что 1 is not добавлено к Array

Четвертая итерация:

• n == 3
• i == 2
• n > nums[i - 1] (3> 1) оценивается как true, а 3 добавляется к Array.

---

Также, если я раскомментирую систему.из линии тогда этогенерирует исключение, поэтому почему nums [i - 1] работает в блоке if для случая, где i = 0?

Это потому, что || - операция короткого замыкания.Это означает, что если одна сторона оценивает значение true, другая сторона не будет оцениваться.Так что в случае, когда i == 0:

if (i == 0 || n > nums[i - 1])
    ^^^^^^--- Evaluates to true. num[i-1] is not considered
    nums[i++] = n;

Затем вы вызываете nums[i++] (который увеличивает i после того, как он помещает n в nums[i]), что составит i 1Затем вы позвоните num[i -1], который будет 0, действительным индексом.

Answer 3

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

Первое число (регистр i==0) всегда входит в результат (поскольку одно число не может быть повторено).

После этого просто проверьте, больше ли текущее наблюдаемое число, чем последнее, которое мы решили сохранить (если оно меньше, ваш массив не был отсортирован, а ваш алгоритм нарушен; если он равен, то это дубликат)и записать его в массив в месте i + 1.