Блог

Главная - Вопросы по программированию - Как составить список с помощью методов set(i, ele), add(), remove() в O(1)?

Как составить список с помощью методов set(i, ele), add(), remove() в O(1)?

#list #data-structures

Вопрос:

В качестве заголовка я хочу составить список с set(i, ele) , add(ele) (at front or at the end) , remove(ele) (at font or at the end) в O(1). Легко выполнить операции добавления() и удаления() в O(1), если мы используем связанный список. Но со связанным списком мы не можем получить доступ к i-му элементу в O(1).

Согласно комментариям, я должен указать add or remove методы, которые работают только в начале или в конце.

Заранее спасибо.

Комментарии:

1. Таким образом, стоимость извлечения (чтения) элемента не указана, не так ли? Затем следует создать журнал всех операций набора, добавления, удаления в связанном списке и следовать списку с самого начала для чтения элемента.

2. remove() если в связанном списке нет O(1), вам нужно выполнить поиск элемента в списке. Если только это не двусвязный список.

3. @Barmar Даже с двусвязным списком вам все равно придется искать элемент. Двойная связь означает только то, что вы также можете выполнять итерации вперед и назад.

4. Почему это помечено тремя разными языками?

5. Похоже, вы могли бы сделать это с помощью словаря python. Конечно, вы не смогли бы вставить новые узлы посередине, но вы об этом не просили, так что-проблема решена!

Ответ №1:

Вы можете использовать хэш-таблицу : вставка, удаление и поиск-это все O(1) в среднем и O(n) в худшем случае

https://en.wikipedia.org/wiki/Hash_table

Комментарии:

1. Спасибо за ответ. 🙂

Ответ №2:

В C вы можете использовать векторный контейнер для вставки, добавления, удаления:

 #include <vector>
#include <iostream>

using namespace std;

void print_vector(vector<int> v) {
    for (auto amp; n : v)
            cout << n << ' ';
    cout << endl;
}

int main(void) {
    vector<int> v = {3,5,6,7};

    print_vector(v);
    v.push_back(8); // add at end of vector
    print_vector(v);

    if (v.size()) // protection
        v.pop_back(); // remove at end of vector
    print_vector(v);

    int i = 3;
    if (v.size <= i) // protection
        v.insert(v.begin()   i, 42); // insert 42 at index i
    print_vector(v);
    return 0;
}

выход:

 3 5 6 7 
3 5 6 7 8 
3 5 6 7 
3 5 6 42 7

Комментарии:

1. удаление элемента посередине из вектора не является O(1)

2. его вопрос не сфокусирован и в любом случае скоро будет закрыт, просто пытаюсь быть полезным и не так много времени 😉 Я думаю, что он хочет удалить в конце вектора, который является O(1) с pop_back()

3. немного вводит в заблуждение, потому что OP запрашивает O(1) стирание, и ваш код стирается, O(1) но в целом это не так O(1)

4. Это невозможно в O(1)

5. это с другим контейнером, а не с std::vector

Метки: , , ,