数据结构:插入,删除,包含,获取随机元素,全部在O(1)

Question

我在接受采访时得到了这个问题.你怎么回答？

设计一个在O(1)时间内提供以下操作的数据结构:

• 插入
• 去掉
• 包含
• 获得随机元素

Answer 1

考虑由哈希表H和数组A组成的数据结构.哈希表键是数据结构中的元素,值是它们在数组中的位置.

1. insert(value):将值附加到数组,让我成为A中的索引.设置H [value] = i.
2. remove(value):我们要用A中的最后一个元素替换A中包含值的单元格.让d成为索引m处数组A中的最后一个元素.让我成为H [value],即要删除的值的数组中的索引.设置A [i] = d,H [d] = i,将数组的大小减小1,并从H中删除值.
3. contains(value):return H.contains(value)
4. getRandomElement():令r = random(当前大小为A).返回A [r].

因为数组需要自动增加大小,所以要分摊O(1)来添加一个元素,但我想这没关系.

Answer 2

O(1)查找意味着散列数据结构.

通过比较:

• O(1)使用O(N)查找插入/删除意味着链表.
• O(1)插入,O(N)删除和O(N)查找意味着支持数组的列表
• O(logN)插入/删除/查找意味着树或堆.

Answer 3

对于这个问题我将使用两个数据结构

• 哈希映射
• ArrayList/数组/双链表。

脚步 ：-

1. 插入：- 检查 X 是否已存在于 HashMap 中 -- 时间复杂度 O(1) 。如果不存在则添加到 ArrayList 的末尾——时间复杂度 O(1)。将其添加到 HashMap 中，同时 x 作为键，最后一个索引作为值——时间复杂度 O(1)。
2. 删除：- 检查 X 是否存在于 HashMap 中 -- 时间复杂度 O(1)。如果存在，则找到其索引并将其从 HashMap 中删除——时间复杂度 O(1)。将此元素与 ArrayList 中的最后一个元素交换并删除最后一个元素——时间复杂度 O(1)。更新HashMap中最后一个元素的索引——时间复杂度O(1)。
3. GetRandom ：- 生成从 0 到 ArrayList 最后一个索引的随机数。返回生成的随机索引处的 ArrayList 元素——时间复杂度 O(1)。
4. 搜索：- 在 HashMap 中查看 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)。

Answer 4

您可能不喜欢这样，因为他们可能正在寻找一个聪明的解决方案，但有时还是值得坚持…… 哈希表已经满足要求 -总体上可能比其他任何方法都更好（尽管显然摊销后的常量时间，以及对其他解决方案的不同妥协）。

棘手的要求是选择“随机元素”：在哈希表中，您需要扫描或探查此类元素。

对于封闭式散列/开放式寻址，任何给定存储桶被占用的机会为size() / capacity()，但至关重要的是，哈希表实现通常将其保持在恒定的乘法范围内（例如，该表可能比其当前内容大1.2倍）。到约10倍，具体取决于性能/内存调整）。这意味着我们平均可以预期搜索1.2到10个桶-完全独立于容器的总大小；摊销O（1）。

我可以想象出两种简单的方法（还有很多更巧妙的方法）：

• 从随机桶中线性搜索

  • 考虑空的/保持价值的桶ala“ --AC ----- B--D”：您可以说第一个“随机”选择是公平的，即使它偏爱B，因为B不再有被偏爱的可能性而不是其他元素，但是如果您使用相同的值进行重复的“随机”选择，那么显然不希望B反复受到青睐（尽管问题中甚至没有要求概率）

• 反复尝试随机存储桶，直到找到一个填充的桶

  • “仅” 访问的平均存储桶（如上）（如上）-但实际上更昂贵，因为随机数生成相对昂贵，并且如果无限不可能的最坏情况，则无限坏...
    • 更快的折衷方案是使用从初始随机选择的存储桶中预先生成的随机偏移量列表，将其％添加到存储桶计数中

这不是一个很好的解决方案，但是与始终保持第二个索引数组的内存和性能开销相比，这可能是一个更好的总体折衷方案。