Найдите самый длинный подмассив, содержащий элемент мажориты

Ответ 1

Примечание: попытка 1 неверна, поскольку @hk6279 предоставил встречный пример. Спасибо, что указали.

Попытка 1: Ответ довольно сложный, поэтому я обсужу краткую идею

Проповедуем каждый уникальный номер один за другим.

Обработка каждого вхождения числа x слева направо, с индексом i, добавление сегмента (i, i) означает начало и конец текущего подмассива. После этого нам нужно взглянуть на левую часть этого сегмента и попытаться объединить левый сосед этого сегмента в (i, i), (Итак, если левый (st, ed), мы попытаемся сделать его (st, i) если он удовлетворяет условию), если это возможно, и продолжать слияние их, пока мы не сможем слиться, или нет левого соседа.

Мы сохраняем все эти сегменты в стеке для более быстрого поиска/добавления/удаления.

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

Сложность времени должна быть O(n), поскольку каждый элемент может быть объединен только один раз.

Попытка 2:

Проповедуем каждый уникальный номер один за другим

Для каждого уникального номера x мы поддерживаем массив счетчиков. От 0 до конца массива, если мы встретим значение x, мы увеличим счетчик, а если мы его не уменьшим, то для этого массива [0,1,2,0,0,3,4,5,0,0] и число 0, у нас есть счетчик массива

[1,0, -1,0,1,0, -1, -2, -1,0]

Итак, чтобы создать допустимый субарак, который заканчивается с определенным индексом i, значение counter[i] - counter[start - 1] должно быть больше 0 (это можно легко объяснить, если вы рассматриваете массив как составляющий от 1 и - 1 запись, с 1 is when there is an occurrence of x, -1 otherwise, и проблема может быть преобразована в поиск подмассива с суммой положительной)

Таким образом, с помощью двоичного поиска указанное выше алгоритм все еще имеет сложность O (n ^ 2 log n) (в случае, если у нас есть n/2 уникальных числа, нам нужно выполнить описанный выше процесс n/2 раз, каждый раз принимают O (n log n))

Чтобы улучшить его, мы делаем замечание о том, что на самом деле нам не нужно хранить все значения для всего счетчика, но только значения счетчика x, мы видели, что мы можем хранить для этого счетчика массива:

[1, #, #, 0,1, #, #, #, - 1,0]

Это приведет к решению O (n log n), которое будет проходить через каждый элемент один раз.

Ответ 2

Это подробно объясняет, как работает попытка 2 в решении @PhamTrung

Чтобы получить длину самого длинного подмассива. Мы должны

• Найти макс. число элемента управления в действительном массиве, обозначаемое как m
  • Это делается попыткой 2 в решении @PhamTrung
• Возврат min (2 * m -1, длина заданного массива)

Концепция

Попытка исходит из метода решения самого длинного положительного субарама

Мы сохраняем массив счетчиков для каждого уникального номера x. Мы выполняем +1, когда сталкиваемся с x. В противном случае сделайте a -1.

Возьмите массив [0,1,2,0,0,3,4,5,0,0,1,0] и уникальный номер 0, у нас есть счетчик массива [1,0, -1,0, 1,0, -1, -2, -1,0, -1,0]. Если мы слепые, это не целевое уникальное число, мы получаем [1, #, #, 0,1, #, #, #, - 1,0, #, 0].

Мы можем получить действительный массив из массива слепых счетчиков, если существует два счетчика, так что значение правого счетчика больше или равно левому. См. Раздел "Доказательство".

Чтобы еще больше улучшить его, мы можем игнорировать все #, поскольку они бесполезны, и мы получаем [1 (0), 0 (3), 1 (4), - 1 (8), 0 (9), 0 (11 )] в формате count (index).

Мы можем улучшить это, если счетчик записей больше, чем его предыдущий эффективный счетчик. В качестве примера возьмем счетчик 8,9, если вы можете сформировать подмассиву с индексом 9, тогда вы должны иметь возможность формировать подмассива с индексом 8. Таким образом, нам нужны только [1 (0), 0 (3), - 1 (8)] для вычисления.

Вы можете сформировать действительный субарейк с текущим индексом со всем предыдущим индексом, используя двоичный поиск в массиве счетчиков, ища самое близкое значение, которое меньше или равно текущему значению счетчика (если найдено)

Доказательство

Когда правый счетчик больше левого счетчика на r для конкретного x, где k, r >= 0, должно быть k + r число x и k число без x существует после левого счетчика. Таким образом,

• Два счетчика находятся в позиции индекса я и r + 2k + i
• Форма подмассива между [i, r + 2k + i] имеет ровно k + r + 1 число x
• Длина подмассива 2k + r + 1
• Подмассив действителен как (2k + r + 1) <= 2 * ( k + r + 1) -1

Процедура

• Пусть m= 1
• Завершить массив слева направо
• Для каждого индекса p _i
  • Если первое встречается,

    • Создать новый массив счетчиков [1 (p _i)]
    • Создать новую индексную запись, сохраняющую текущее значение индекса (p _i) и значение счетчика (1)

  • В противном случае повторно используйте массив счетчиков и индексный массив номера и выполните

    • Рассчитать текущее значение счетчика c _i c _prev + 2- (p _i - p _prev), где c _prev, p _prev - значение счетчика и значение индекса в записи индекса
    • Выполните двоичный поиск, чтобы найти самый длинный подмассив, который может быть сформирован с текущей позицией индекса и всей предыдущей позицией индекса. т.е. Найдите ближайший c, c _{ближайший}, в массиве счетчиков, где c <= c _i. Если не найден, перейдите к шагу 5

    • Рассчитать количество x в подмассиве, найденном на шаге 2

      r = c _i - c _{ближайший}

      k = (p _i -p _{ближайший} -r)/2

      число x= k + r + 1

    • Обновить счетчик m по номеру x, если в подмассиве есть число x > m
    • Обновить массив счетчиков, добавив текущий счетчик, если значение счетчика меньше последнего записанного значения счетчика
    • Обновить индексную запись по текущему индексу (p _i) и значение счетчика (c _i)

Ответ 3

Алгоритм: По сути, то, что делает Boyer-Moore, это поиск суффикса sufsuf nums, где suf [0] suf [0] - это элемент большинства в этом суффиксе. Для этого мы поддерживаем подсчет, который увеличивается, когда мы видим экземпляр нашего текущего кандидата для элемента большинства и уменьшаем каждый раз, когда видим что-либо еще. Всякий раз, когда count равно 0, мы фактически забываем обо всем в nums до текущего индекса и рассматриваем текущее число как кандидат на элемент большинства. Не сразу понятно, почему мы можем уйти с забыванием префиксов nums - рассмотрим следующие примеры (трубы вставляются в отдельные прогоны ненулевого подсчета).

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

Здесь 7 в индексе 0 выбирается как первый кандидат для элемента большинства. счет будет в конечном итоге достигнут 0 после обработки индекса 5, поэтому 5 с индексом 6 будет следующим кандидатом. В этом случае 7 является истинным элементом большинства, поэтому, не обращая внимания на этот префикс, мы игнорируем равное количество элементов большинства и меньшинства, поэтому 7 будет оставаться элементом большинства в суффиксе, образованным путем выброса первого префикса.

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]

Теперь элемент большинства - 5 (мы изменили последний пробег массива с 7s до 5s), но наш первый кандидат все еще остается 7. В этом случае наш кандидат не является истинным элементом большинства, но мы все еще не можем отбросить больше элементов большинства, чем элементы меньшинства (это означало бы, что count может достигнуть -1, прежде чем переназначить кандидата, что, очевидно, неверно).

Поэтому, учитывая, что невозможно (в обоих случаях) отказаться от большинства элементов большинства, чем элементы меньшинства, мы можем отбросить префикс и попытаться рекурсивно решить проблему элементарного элемента для суффикса. В конце концов будет найден суффикс, для которого счетчик не достигнет 0, а элемент большинства этого суффикса обязательно будет таким же, как и элемент большинства из общего массива.

Здесь решение Java:

• Сложность времени: O (n)

• Сложность пространства: O (1)

  public int majorityElement(int[] nums) {
      int count = 0;
      Integer candidate = null;
  
      for (int num : nums) {
          if (count == 0) {
              candidate = num;
          }
          count += (num == candidate) ? 1 : -1;
      }
  
      return candidate;
  }