Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 40

Минимальное количество сравнений, необходимое для определения, появляется ли целое число более чем в n / 2 раза в отсортированном массиве из n целых чисел, равно

(A) Θ (n)
(B) Θ (logn)
(C) Θ (log * n)
(D) Θ (1)

Ответ: (Б)
Объяснение: Если вы ответили на Theta (1), подумайте о примерах {1, 2, 2, 2, 4, 4}, {1, 1, 2, 2, 2, 2, 3, 3}

Лучший способ выяснить, встречается ли целое число более чем в n / 2 раза в отсортированном массиве (в порядке возрастания) из n целых чисел, — это подход двоичного поиска.

  1. Первое вхождение элемента может быть обнаружено за время O (log (n)) с использованием техники «разделяй и властвуй», скажем, это i.
  2. Последнее вхождение элемента может быть обнаружено за время O (log (n)) с использованием техники «разделяй и властвуй», скажем, это j.
  3. Теперь номер вхождения этого элемента (count) равен (j-i + 1). Общая сложность времени = log n + log n +1 = O (logn)

См. Проверка на элемент большинства в отсортированном массиве.

Это решение предоставлено Nirmal Bharadwaj
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2008 | Вопрос 40

0.00 (0%) 0 votes