Структура данных: вставить, удалить, содержит, получить случайный элемент, все в O(1)

O(1) Поиск подразумевает a хэшированная структура данных.

для сравнения:

• O(1) insert/delete with O (N) lookup подразумевает связанный список.
• за O(1) вставка за o(n) и удалить, и О(П) поиск подразумевает массив резервного списка
• o(logN) вставка/удаление/поиск подразумевает дерево или кучу.

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

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

для закрытого хэширования / открытой адресации вероятность того, что какое-либо ведро будет занято, равна size() / capacity(), но принципиально это обычно хранится в постоянном мультипликативном диапазоне с помощью реализации хэш-таблицы (например, таблица может храниться больше, чем ее текущее содержимое, скажем, от 1,2 x до ~10x в зависимости от производительности/настройки памяти). Это означает, что в среднем мы можем ожидать поиска от 1,2 до 10 ведер-полностью независимо от общего размера контейнера; амортизированный O (1).

Я могу представить себе два простых подхода (и очень много более сложных):

• поиск линейно из случайного ведра

  • рассмотрим пустые / значение-холдинг ведра Ала "--AC - - - - - B--D": вы можете скажем, что первый "случайный" выбор справедлив, даже если он благоприятствует B, потому что B не имел большей вероятности быть благоприятным, чем другие элементы, но если вы делаете повторные "случайные" выборы, используя то же самое значения тогда ясно, что многократно одобренные B могут быть нежелательными (ничто в вопросе не требует даже вероятностей)

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

  • "только" способность() / размер() в среднем ведра посетил (как и выше) - но в практическом плане дороже, потому что генерация случайных чисел является относительно дорогим, и бесконечно плохо, если бесконечно маловероятно худший случай поведение...
    • более быстрым компромиссом было бы использовать список предварительно сгенерированных случайных смещений от начального случайно выбранного ведра, % - ing их в счетчик ведра

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

лучшим решением, вероятно, является хэш-таблица + массив, это очень быстро и детерминировано.

но самый низкий рейтинг ответ (просто используйте хэш-таблицу!) на самом деле тоже здорово!

• хэш-таблица с повторным хэшированием или новым выбором ведра (т. е. один элемент на ведро, без связанных списков)
• getRandom () неоднократно пытается выбрать случайное ведро, пока оно не опустеет.
• как отказоустойчивый, возможно getRandom (), после n (количество элементов) неудачно пытается, выбирает случайный индекс i в [0, N-1], а затем проходит через хеш-таблицу линейно и выбирает #i-й элемент.

людям это может не понравиться Из-за" возможных бесконечных циклов", и я видел, что у очень умных людей тоже есть такая реакция, но это неправильно! Бесконечно маловероятные события просто не произойдет.

предполагая хорошее поведение вашего псевдослучайного источника - что нетрудно установить для этого конкретного поведения - и этот хэш таблицы всегда заполнены не менее чем на 20%, это легко увидеть:

Это никогда бывает, что getRandom () должен попробовать более 1000 раз. Просто никогда. Действительно, вероятность такого события равна 0,8^1000, что составляет 10^-97 , поэтому нам пришлось бы повторить его 10^88 раз, чтобы иметь один шанс из миллиарда когда-либо происходящих один раз. Даже если эта программа работала полный рабочий день на всех компьютерах человечества, пока солнце не умрет, это будет никогда случаться.

вот C# решение этой проблемы я придумал некоторое время назад, когда задал тот же вопрос. Он реализует Add, Remove, Contains и Random вместе с другими стандартными интерфейсами .NET. Не то, чтобы вам когда-либо нужно было бы реализовать его так подробно во время интервью, но приятно иметь конкретное решение, чтобы посмотреть...

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

/// <summary>
/// This class represents an unordered bag of items with the
/// the capability to get a random item.  All operations are O(1).
/// </summary>
/// <typeparam name="T">The type of the item.</typeparam>
public class Bag<T> : ICollection<T>, IEnumerable<T>, ICollection, IEnumerable
{
    private Dictionary<T, int> index;
    private List<T> items;
    private Random rand;
    private object syncRoot;

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    public Bag()
        : this(0)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    /// <param name="capacity">The capacity.</param>
    public Bag(int capacity)
    {
        this.index = new Dictionary<T, int>(capacity);
        this.items = new List<T>(capacity);
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    /// <param name="collection">The collection.</param>
    public Bag(IEnumerable<T> collection)
    {
        this.items = new List<T>(collection);
        this.index = this.items
            .Select((value, index) => new { value, index })
            .ToDictionary(pair => pair.value, pair => pair.index);
    }

    /// <summary>
    /// Get random item from bag.
    /// </summary>
    /// <returns>Random item from bag.</returns>
    /// <exception cref="System.InvalidOperationException">
    /// The bag is empty.
    /// </exception>
    public T Random()
    {
        if (this.items.Count == 0)
        {
            throw new InvalidOperationException();
        }

        if (this.rand == null)
        {
            this.rand = new Random();
        }

        int randomIndex = this.rand.Next(0, this.items.Count);
        return this.items[randomIndex];
    }

    /// <summary>
    /// Adds the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    public void Add(T item)
    {
        this.index.Add(item, this.items.Count);
        this.items.Add(item);
    }

    /// <summary>
    /// Removes the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <returns></returns>
    public bool Remove(T item)
    {
        // Replace index of value to remove with last item in values list
        int keyIndex = this.index[item];
        T lastItem = this.items[this.items.Count - 1];
        this.items[keyIndex] = lastItem;

        // Update index in dictionary for last item that was just moved
        this.index[lastItem] = keyIndex;

        // Remove old value
        this.index.Remove(item);
        this.items.RemoveAt(this.items.Count - 1);

        return true;
    }

    /// <inheritdoc />
    public bool Contains(T item)
    {
        return this.index.ContainsKey(item);
    }

    /// <inheritdoc />
    public void Clear()
    {
        this.index.Clear();
        this.items.Clear();
    }

    /// <inheritdoc />
    public int Count
    {
        get { return this.items.Count; }
    }

    /// <inheritdoc />
    public void CopyTo(T[] array, int arrayIndex)
    {
        this.items.CopyTo(array, arrayIndex);
    }

    /// <inheritdoc />
    public bool IsReadOnly
    {
        get { return false; }
    }

    /// <inheritdoc />
    public IEnumerator<T> GetEnumerator()
    {
        foreach (var value in this.items)
        {
            yield return value;
        }
    }

    /// <inheritdoc />
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    /// <inheritdoc />
    public void CopyTo(Array array, int index)
    {
        this.CopyTo(array as T[], index);
    }

    /// <inheritdoc />
    public bool IsSynchronized
    {
        get { return false; }
    }

    /// <inheritdoc />
    public object SyncRoot
    {
        get
        {
            if (this.syncRoot == null)
            {
                Interlocked.CompareExchange<object>(
                    ref this.syncRoot,
                    new object(),
                    null);
            }

            return this.syncRoot;

        }
    }
}

хотя это очень старый, но так как в C++ нет ответа, вот мои два цента.

#include <vector>
#include <unordered_map>
#include <stdlib.h>

template <typename T> class bucket{
    int size;
    std::vector<T> v;
    std::unordered_map<T, int> m;
public:
    bucket(){
        size = 0;
        std::vector<T>* v = new std::vector<T>();
        std::unordered_map<T, int>* m = new std::unordered_map<T, int>();
    }
    void insert(const T& item){
        //prevent insertion of duplicates
        if(m.find(item) != m.end()){
            exit(-1);
        }
        v.push_back(item);
        m.emplace(item, size);
        size++;

    }
    void remove(const T& item){
        //exits if the item is not present in the list
        if(m[item] == -1){
            exit(-1);
        }else if(m.find(item) == m.end()){
            exit(-1);
        }

        int idx = m[item];
        m[v.back()] = idx;
        T itm = v[idx];
        v.insert(v.begin()+idx, v.back());
        v.erase(v.begin()+idx+1);
        v.insert(v.begin()+size, itm);
        v.erase(v.begin()+size);
        m[item] = -1;
        v.pop_back();
        size--;

    }

     T& getRandom(){
      int idx = rand()%size;
      return v[idx];

     }

     bool lookup(const T& item){
       if(m.find(item) == m.end()) return false;
       return true;

     }
    //method to check that remove has worked
    void print(){
        for(auto it = v.begin(); it != v.end(); it++){
            std::cout<<*it<<" ";
        }
    }
};

вот фрагмент клиентского кода для тестирования решения.

int main() {

    bucket<char>* b = new bucket<char>();
    b->insert('d');
    b->insert('k');
    b->insert('l');
    b->insert('h');
    b->insert('j');
    b->insert('z');
    b->insert('p');

    std::cout<<b->random()<<std::endl;
    b->print();
    std::cout<<std::endl;
    b->remove('h');
    b->print();

    return 0;
}

для этого вопроса я буду использовать две структуры данных

• HashMap
• ArrayList / Array / Double LinkedList.

шагов :-

1. вставка: - проверьте, если X уже присутствует в HashMap --Time complexity O (1) . если нет, то добавьте в конец ArrayList -- Time complexity O (1). добавьте его в HashMap также x как ключ и последний индекс как значение -- временная сложность O(1).
2. удалить : - проверьте, если X присутствует в HashMap --временная сложность O (1). Если присутствует, то найдите его индекс и удалите его из HashMap --Time complexity O(1). замените этот элемент последним элементом в ArrayList и удалите последний элемент --Time complexity O(1). Обновите индекс последнего элемента в HashMap --Time complexity O (1).
3. GetRandom: - генерировать случайное число от 0 до последнего индекса ArrayList . возвращает элемент ArrayList в произвольном индексе, сгенерированном --Time complexity O (1).
4. поиск: в частности, X как ключ. --За время O(1).

код :-

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;


public class JavaApplication1 {

    public static void main(String args[]){
       Scanner sc = new Scanner(System.in);
        ArrayList<Integer> al =new ArrayList<Integer>();
        HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();  
        while(true){
            System.out.println("**menu**");
            System.out.println("1.insert");
            System.out.println("2.remove");
            System.out.println("3.search");
            System.out.println("4.rendom");
            int ch = sc.nextInt();
            switch(ch){
                case 1 : System.out.println("Enter the Element ");
                        int a = sc.nextInt();
                        if(mp.containsKey(a)){
                            System.out.println("Element is already present ");
                        }
                        else{
                            al.add(a);
                            mp.put(a, al.size()-1);

                        }
                        break;
                case 2 : System.out.println("Enter the Element Which u want to remove");
                        a = sc.nextInt();
                        if(mp.containsKey(a)){

                            int size = al.size();
                            int index = mp.get(a);

                            int last = al.get(size-1);
                            Collections.swap(al, index,  size-1);

                            al.remove(size-1);
                            mp.put(last, index);

                            System.out.println("Data Deleted");

                        }
                        else{
                            System.out.println("Data Not found");
                        }
                        break;
                case 3 : System.out.println("Enter the Element to Search");
                        a = sc.nextInt();
                        if(mp.containsKey(a)){
                            System.out.println(mp.get(a));
                        }
                        else{
                            System.out.println("Data Not Found");
                        }
                        break;
                case 4 : Random rm = new Random();
                        int index = rm.nextInt(al.size());
                        System.out.println(al.get(index));
                        break;

            }
        }
    }

}

-- временная сложность O (1). -- Сложность пространства O (N).

в C# 3.0 + .NET Framework 4, Общий Dictionary<TKey,TValue> даже лучше, чем хэш-таблица, потому что вы можете использовать System.Linq метод расширения ElementAt() индексировать в базовый динамический массив, где KeyValuePair<TKey,TValue> элементы хранятся :

using System.Linq;

Random _generator = new Random((int)DateTime.Now.Ticks);

Dictionary<string,object> _elements = new Dictionary<string,object>();

....

Public object GetRandom()
{
     return _elements.ElementAt(_generator.Next(_elements.Count)).Value;
}

однако, насколько я знаю, хэш-таблица (или ее словарное потомство) не является реальным решением этой проблемы , потому что Put() может быть амортизирован только O(1), а не истинным O(1), потому что это O(N) на границе динамического изменения размера.

Is есть реальное решение этой проблемы ? Все, о чем я могу думать, это если вы укажете начальную емкость словаря/хэш-таблицы на порядок выше того, что вы ожидаете когда-либо, тогда вы получите O(1) операции, потому что вам никогда не нужно изменять размер.

мы можем использовать хэширование для поддержки операций в Θ (1) времени.

вставить(x) 1) Проверьте, если x уже присутствует, выполнив поиск хэш-карты. 2) Если нет, то вставьте его в конце массива. 3) Добавить в хэш-таблицу также, x добавляется как ключ и последний индекс массива в качестве индекса.

удалить(x) 1) Проверьте, присутствует ли x, выполнив поиск хэш-карты. 2) если присутствует, то найдите его индекс и удалите его из хэш-карты. 3) поменять местами последний элемент с этим элемент в массиве и удалить последний элемент. Обмен происходит потому, что последний элемент может быть удален в O(1) времени. 4) обновить индекс последнего элемента в хэш-карте.

getRandom() 1) генерировать случайное число от 0 до последнего индекса. 2) возвращает элемент массива по случайно сгенерированному индексу.

поиск (x) Выполните поиск x в хэш-карте.

Я согласен с Аноном. За исключением последнего требования, где требуется получение случайного элемента с равной справедливостью, все остальные требования могут быть решены только с использованием одного хэш-кода на основе DS. Я выберу HashSet для этого в Java. Модуль хэш-кода элемента даст мне индекс no базового массива в O (1) раз. Можно использовать для добавления, удаления и содержит операции.

не можем ли мы сделать это с помощью HashSet Java? Он предоставляет insert, del, search all in O (1) по умолчанию. Для getRandom мы можем использовать итератор множества, который в любом случае дает случайное поведение. Мы можем просто повторить первый элемент из набора, не беспокоясь об остальных элементах

public void getRandom(){
    Iterator<integer> sitr = s.iterator();
    Integer x = sitr.next();    
    return x;
}

/* Java program to design a data structure that support folloiwng operations
   in Theta(n) time
   a) Insert
   b) Delete
   c) Search
   d) getRandom */
import java.util.*;

// class to represent the required data structure
class MyDS
{
   ArrayList<Integer> arr;   // A resizable array

   // A hash where keys are array elements and vlaues are
   // indexes in arr[]
   HashMap<Integer, Integer>  hash;

   // Constructor (creates arr[] and hash)
   public MyDS()
   {
       arr = new ArrayList<Integer>();
       hash = new HashMap<Integer, Integer>();
   }

   // A Theta(1) function to add an element to MyDS
   // data structure
   void add(int x)
   {
      // If ekement is already present, then noting to do
      if (hash.get(x) != null)
          return;

      // Else put element at the end of arr[]
      int s = arr.size();
      arr.add(x);

      // And put in hash also
      hash.put(x, s);
   }

   // A Theta(1) function to remove an element from MyDS
   // data structure
   void remove(int x)
   {
       // Check if element is present
       Integer index = hash.get(x);
       if (index == null)
          return;

       // If present, then remove element from hash
       hash.remove(x);

       // Swap element with last element so that remove from
       // arr[] can be done in O(1) time
       int size = arr.size();
       Integer last = arr.get(size-1);
       Collections.swap(arr, index,  size-1);

       // Remove last element (This is O(1))
       arr.remove(size-1);

       // Update hash table for new index of last element
       hash.put(last, index);
    }

    // Returns a random element from MyDS
    int getRandom()
    {
       // Find a random index from 0 to size - 1
       Random rand = new Random();  // Choose a different seed
       int index = rand.nextInt(arr.size());

       // Return element at randomly picked index
       return arr.get(index);
    }

    // Returns index of element if element is present, otherwise null
    Integer search(int x)
    {
       return hash.get(x);
    }
}

// Driver class
class Main
{
    public static void main (String[] args)
    {
        MyDS ds = new MyDS();
        ds.add(10);
        ds.add(20);
        ds.add(30);
        ds.add(40);
        System.out.println(ds.search(30));
        ds.remove(20);
        ds.add(50);
        System.out.println(ds.search(50));
        System.out.println(ds.getRandom());`enter code here`
    }
}

Я думаю, что мы можем использовать двойной список ссылок с хэш-таблицей. ключ будет элементом, а его ассоциированное значение будет узлом в двойном linklist.

1. insert (H, E): вставить узел в двойной linklist и сделать запись как H[E]=node; O(1)
2. delete ( H, E): получить адрес узла По H(E), перейти к предыдущему из этого узла и удалить и сделать H(E) как NULL, так что O(1)
3. содержит(H, E) и getRandom(H) очевидно O(1)