Найти все индексы данного элемента в отсортированной форме данного массива

Опубликовано: 20 Сентября, 2022

Дан массив arr[] целых чисел размера N и целевое значение val . Ваша задача — найти индексы val в массиве после сортировки массива по возрастанию .

Примечание: индексы должны быть в порядке возрастания.

Примеры:

Input: arr = [1, 2, 5, 2, 3], val = 2
Output: 1 2
Explanation: After sorting, arr[] becomes [1, 2, 2, 3, 5]. The indices where arr[i] = 2 are 1 and 2. As the indices should be in increasing order, that’s why they are   (1, 2) and not (2, 1)

Input: arr = [1, 2, 5, 2, 3], val = 6
Output: []
Explanation: After sorting, nums is [1, 2, 2, 3, 5]. The value 6 is not present in the array. 

Наивный подход: концепция этого подхода основана на сортировке . Массив отсортирован в порядке возрастания. Затем просматривается отсортированный массив. При обходе массива, если какое-либо значение соответствует цели, этот индекс добавляется в список ответов. После завершения итерации возвращается список ответов.
Временная сложность: O(N*logN)
Вспомогательное пространство: O(1)

Эффективный подход: этот подход основан на наблюдении за отсортированным массивом. В массиве, отсортированном по возрастанию , все элементы перед val меньше val. Итак, чтобы получить индексы val в отсортированном массиве, вместо выполнения операции сортировки мы можем просто подсчитать элементы меньше , чем val . Если счетчик равен x, то val будет начинаться с x-го индекса (из-за индексации на основе 0). Выполните шаги, указанные ниже:

  • Пройдитесь по массиву. Используйте переменные для хранения количества элементов меньше val ( smallCount ) и элементов, имеющих значение такое же, как val ( sameCount ).
  • Если значение элемента меньше val, увеличьте smallCount на единицу.
  • Если значение совпадает с val , увеличьте sameCount на единицу.
  • После завершения обхода индексы будут начинаться с smallCount и заканчиваться на (smallCount+sameCount-1)

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ