Рубрики

Структура данных для n элементов и O (1) операций

Массивы

Предложите структуру данных для следующего:
Структура данных будет содержать элементы от 0 до n-1. На элементах нет порядка (нет требований к возрастанию / убыванию)

Сложность операций должна быть следующей:
* Вставка элемента — O (1)
* Удаление элемента — O (1)
* Нахождение элемента — O (1)

Мы настоятельно рекомендуем свернуть браузер и попробовать это в первую очередь.

Здесь работает логический массив. Массив будет иметь значение «истина» в i-м индексе, если он присутствует, и «ложь», если он отсутствует.

Инициализация:
Мы создаем массив размером n и инициализируем все элементы как отсутствующие.

void initialize(int n)

{

  bool A[n];

  for (int i = 0; i<n; i++)

    A[i] = {0}; // или A [n] = {false};

}

Вставка элемента:

void insert(unsigned i)

{

   / * установить значение индекса i в true * /

   A[i] = 1; // Или A [i] = true;

}

Удаление элемента:

void delete(unsigned i)

{

  / * сделать значение индекса i равным 0 * /

  A[i] = 0;  // Или A [i] = false;

}

Нахождение элемента:

// Возвращает true, если присутствует «i», иначе false

bool find(unsigned i)

{

    return A[i];

}

В качестве упражнения измените структуру данных так, чтобы она содержала значения от 1 до n вместо 0 до n-1.

Эта статья предоставлена Sachin . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Структура данных для n элементов и O (1) операций

0.00 (0%) 0 votes