针对给定操作设计高效的数据结构

为了针对特定操作设计高效的数据结构，所创建的数据结构的给定操作的时间和空间复杂度非常重要。让我们看看一些基本操作以及如何有效地优化它们：

  • insert() − 将元素插入到数据结构中

    动态数组、哈希表、二叉搜索树和平衡搜索树（如AVL树或红黑树）是提供插入操作O(1)复杂度的最有效的数据结构选择。

  • delete() − 从数据结构中删除元素

    哈希表以O(1)的时间处理删除过程，而二叉搜索树和平衡搜索树（如AVL树或红黑树）则需要O(logN)的时间来进行删除操作。

  • search() − 在数据结构中搜索给定元素，并返回它是否存在

    带单独链的哈希表和HashMap搜索操作需要O(1)的时间，而二叉搜索树和平衡搜索树（如AVL树或红黑树）则需要O(logN)的时间进行搜索操作。

  • getRandom() − 返回数据结构中存储的随机元素

    具有随机洗牌功能的动态数组和HashMap提供从数据结构中获取随机元素的O(1)复杂度，而像AVL树或红黑树这样的平衡搜索树则需要o(logN)的时间来执行相同的操作。

问题陈述

设计一个高效的数据结构，使其具有最小的時間和空间复杂度，以执行以下操作：

  • insert()

  • remove()

  • search()

  • getRandom()

  • removeRandom()

  • size()

示例

输入

  • insert(2)

  • insert(3)

  • insert(4)

  • search(6)

  • getRandom()

  • remove(2)

  • size()

  • removeRandom()

输出

  • -

  • -

  • -

  • False

  • 3

  • -

  • 2

  • 4

解释

数据结构初始化：A ={}

  • 插入2后：A={2}

  • 插入3后：A={2,3}

  • 插入4后：A={2,3,4}

  • 在A中搜索6：False

  • 从A中获取随机元素：3

  • 从A中删除2：A={3,4}

  • 数据结构的大小为2

  • 从A中删除随机元素：A={3}（删除并返回4）

解决方案方法

使用以下方法定义我们的数据结构：

  • 无序映射 − 它将数据结构的元素存储为键，并将它们在动态数组中的索引作为值。它用于允许高效地访问和删除元素。

  • 动态数组 − 它按插入顺序存储数据结构的元素。它允许随机函数高效工作。

  • 随机数生成器

算法

  • 初始化一个空集合（元素）来按添加元素的顺序存储值。

  • 初始化一个哈希映射，其键为元素，值为存储在集合中的元素的索引。

  • 初始化一个随机数生成器。

  • 实现以下方法：

    • insert(ele) − 如果元素不存在，则将其添加到集合中，并将索引与元素一起添加到哈希映射中。

    • search(ele) − 通过搜索哈希映射来搜索元素。

    • getRandom() − 随机数生成器生成一个随机索引，并返回该索引处的元素。

    • removeRandom() − 随机数生成器生成一个随机索引，并将该索引处的元素从集合和哈希映射中删除。

    • remove() − 通过从哈希映射中获取其索引并从集合和哈希映射中删除元素来删除特定元素。

    • size() − 返回集合的大小。

示例

Open Compiler
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stdexcept>
#include <random>
#include <ctime>
#include <algorithm>

template <typename T>
class RandomizedSet {
private:
   std::unordered_map<T, int> elementIndexes;
   std::vector<T> element;
   std::mt19937 rand;

public:
   RandomizedSet() {
      elementIndexes.clear();
      element.clear();
      rand = std::mt19937(std::time(0));
   }

   void insert(T ele) {
      if (!search(ele)) {
         int lastIndex = element.size();
         elementIndexes[ele] = lastIndex;
         element.push_back(ele);
      }
   }
   bool search(T ele) {
      return elementIndexes.find(ele) != elementIndexes.end();
   }
   T getRandom() {
      if (elementIndexes.empty()) {
         throw std::out_of_range("Empty set, cannot get a random element.");
      }
      std::uniform_int_distribution<int> dist(0, element.size() - 1);
      int randomIndex = dist(rand);
      return element[randomIndex];
   }
   T removeRandom() {
      if (elementIndexes.empty()) {
         throw std::out_of_range("Empty set, cannot remove a random element.");
      }
      std::uniform_int_distribution<int> dist(0, element.size() - 1);
      int randomIndex = dist(rand);
      return removeElement(randomIndex); // Corrected function name
   }
   T remove(T ele) {
      if (!search(ele)) {
         throw std::out_of_range("Element not found in the set.");
      }
      int index = elementIndexes[ele];
      return removeElement(index); // Corrected function name
   }
   int size() {
      if (element.size() != elementIndexes.size()) {
         throw std::runtime_error("Inconsistent set size, internal error.");
      }
      return element.size();
   }

private:
   T removeElement(int currentIndex) { // Corrected function name
      T currentElement = element[currentIndex];
      int lastIndex = element.size() - 1;
      T lastVal = element[lastIndex];
      std::swap(element[currentIndex], element[lastIndex]);
      element.pop_back();
      elementIndexes[lastVal] = currentIndex;
      elementIndexes.erase(currentElement);
      return currentElement;
   }
};

#include <iostream>

int main() {
   // Create an instance of the RandomizedSet for integers
   RandomizedSet<int> mySet;

   // Insert elements
   mySet.insert(42);
   mySet.insert(99);

   // Check if an element exists
   bool exists = mySet.search(42);

   // Remove a specific element
   mySet.remove(42);

   // Get a random element
   int randomElement = mySet.getRandom();

   // Get the size of the set
   int setSize = mySet.size();

   // Output results
   std::cout << "Element 42 exists: " << exists << std::endl;
   std::cout << "Random element: " << randomElement << std::endl;
   std::cout << "Set size: " << setSize << std::endl;

   return 0;
}

输出

Element 42 exists: 1
Random element: 99
Set size: 1

时间复杂度：

  • insert() = O(1)

  • search() = O(1)

  • getRandom() = O(1)

  • removeRandom() = O(1)

  • remove() = O(1)

  • size() = O(1)

空间复杂度：

  • element[] 数组 = O(n)

  • elementIndexes 哈希映射 = O(n)

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

总之，RandomizedSet结构提供了一种高效的方法来执行具有O(1)复杂度的函数。这些操作包括insert、search、getRandom、removeRandom、remove和size。

更新于：2023年11月3日

浏览量：243

开启你的职业生涯

完成课程获得认证

开始学习
广告