資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學針對給定操作設計高效的資料結構
為了針對特定操作設計高效的資料結構，所建立的資料結構的給定操作的時間和空間複雜度非常重要。讓我們看看一些基本操作以及如何有效地最佳化它們：
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() − 返回集合的大小。
示例
#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)
結論
總之，RandomizedSet結構提供了一種高效的方法來執行具有O(1)複雜度的函式。這些操作包括insert、search、getRandom、removeRandom、remove和size。
瀏覽量：243
