使用排序数组实现集合

Question

这是一道数据结构题，也是关于实现的题。集合通常使用 BST 实现，但我的教授希望我们知道如何在仅提供有限选项时实现某些数据结构。所以他希望我们能够理解如何只使用一个数组来创建一个集合。

使用标准（未排序）数组我理解 implementation/complexity...

void add(Student[] arr, Student findstu)
{
    Student stu = new Student();
    int i=0;
    boolean found = false;
    while(stu!=NULL)
    {
        stu = arr[i++];
        if (stu==findstu)
        {
             found = true;
        }
     }
    if (found==false)
    {
         arr[i+1] = findstu;
    }
 }

add/remove/contains 是几乎相同的代码，都有第一个 while 循环，这将使它们成为 O(n)。

但是如果我们使用排序数组，为什么包含是 O(lgn) 和 add/remove O(n)？

Answer 1

搜索将是 O(logN)，因为由于数组已排序，您可以应用具有 O(logN) 复杂度的二进制搜索。

插入和擦除会 O(N) 复杂（即，线性时间），因为每次您尝试在排序数组中插入或擦除一个元素时，您都必须将数组的元素移动一个位置这是 O(N) 线性时间复杂度。

使用排序数组实现集合

Implementing a Set Using a Sorted Array

c++

arrays

set