資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究查詢陣列中的元素並在每次查詢後將其移到最前面
介紹
在本教程中，任務是使用查詢在陣列中搜索元素。它是在每次 C++ 查詢後將其推送到最前面。為了實現此任務，它採用了一個包含 1 到 5 個元素的陣列 A 和一個用於在 A 中查詢元素並將其移動到陣列開頭的查詢陣列 Q。輸出是已搜尋元素的索引號。我們根據查詢陣列使用兩種方法將陣列元素移動到最前面。
樸素方法 - 使用雜湊表搜尋這些元素時，遍歷元素陣列。
使用 Fenwick 樹 進行搜尋和更新新陣列 - Fenwick 樹或二進位制索引樹是一種高效的資料結構，用於頻繁更新陣列和查詢。
演示
Input = Q[] = {3, 2, 2, 3} A = 5
Output = The indices after moving query element to the front are 2 2 0 1
解釋
上面演示中的陣列是 [1, 2, 3, 4, 5]。使用查詢陣列 [3, 2, 2, 3] 查詢該陣列元素的索引。按照以下方式計算更新後的陣列：
查詢 1 - 查詢 3，此元素在陣列 A 中的索引為 2。將結果元素移動到更新後陣列的前面。
搜尋索引 2 處的 3 並將元素移動到前面後。更新後的陣列為 {3, 1, 2, 4, 5}。
查詢 2 - 查詢 2，此元素在陣列 A 中的索引為 2。將結果元素移動到更新後陣列的前面。
搜尋索引 2 處的 2 並將元素移動到前面後。更新後的陣列為 {2, 3, 1, 4, 5}。
查詢 3 - 查詢 2，此元素在陣列 A 中的索引為 0。將結果元素移動到更新後陣列的前面。
搜尋索引 2 處的 2 並將元素移動到前面後。更新後的陣列為 {2, 3, 1, 4, 5}。
查詢 4 - 查詢 3，此元素在陣列 A 中的索引為 1。將結果元素移動到更新後陣列的前面。
搜尋索引 1 處的 3 並將其移動到前面後。更新後的陣列為 {3, 2, 1, 4, 5}。結果是 2 2 0 1。
C++ 庫函式
sizeof() - 這是一個標準的 C++ 庫函式。它在編譯時計算陣列、變數或資料型別的 size。
sizeof(variable);
Vector - 它是 C++ 中的動態陣列。它在 <vector> 標頭檔案中定義。它提供更快、更有效的陣列元素更新和刪除。
vector<data_type> vector_name;
swap() - 這是一個預定義的 C++ 庫函式。它交換或互換兩個元素的位置。它採用兩個引數進行交換。
swap(value1, value2);
push_back() - 它是 vector 類的預定義函式，在 <vector> 標頭檔案中定義。它將元素推入或插入到 vector 陣列的末尾。
vector_name.push_back(value);
unordered_map() - 它是 C++ 中的一個容器類，用於儲存對映值和鍵值對中的資料。它增強了陣列函式（如更新、刪除、插入）的處理。
unordered_map<data_type> unordered_map_name;
演算法
初始化查詢陣列並取另一個數組 5 的值。
查詢表示陣列的索引。
使用雜湊表根據查詢搜尋陣列元素。
透過交換更新新陣列，同時將搜尋到的元素移動到前面。
列印結果。
示例 1
在這裡，我們用 C++ 實現問題陳述。我們使用一種基本方法，其中包括一個雜湊表，用於根據查詢陣列的索引搜尋元素。搜尋元素後，在更新陣列 A 的同時將其移動到陣列的前面。
#include <bits/stdc++.h>
using namespace std;
// user-defined function for query processing
vector<int> processingQueries(int Q[], int a, int s){
int f[a + 1], p[a + 1];
for (int x = 1; x <= a; x++){
f[x - 1] = x;
p[x] = x - 1;
}
vector<int> result;
// iterating array for query
for (int x = 0; x < s; x++){
int qa = Q[x];
int ps = p[qa];
result.push_back(ps);
for (int x = ps; x > 0; x--){
// swapping element positions
swap(f[x], f[x - 1]);
p[f[x]] = x;
}
p[f[0]] = 0;
}
// returning result
return result;
}
// code controller
int main(){
// query array
int Q[] = { 4, 1, 2, 1 };
int s = sizeof(Q) / sizeof(Q[0]);
int a = 5;
vector<int> result;
// calling function
result = processingQueries(Q, a, s);
// Printing the output after queries
cout<< "Updated array after searching the elements is: ";
for (int x = 0; x < result.size(); x++)
cout << result[x] << " ";
return 0;
}
輸出
Updated array after searching the elements is: 3 1 2 1
示例 2
我們使用 Fenwick 樹（一種二進位制索引樹）在 C++ 中實現問題陳述。初始化一個用於查詢的陣列，並使用 Fenwick 樹在陣列“a”中搜索查詢元素。不要將 0 的索引值分配給陣列，而是將 -1 索引值分配給查詢 1，將 -2 分配給查詢 2，依此類推。
#include <bits/stdc++.h>
using namespace std;
// Function for updating the fenwick tree
void updateArray(vector<int>& Fentree, int x, int v){
while (x < Fentree.size()) {
Fentree[x] += v;
x += (x & (-x));
}
}
int calSum(vector<int>& Fentree, int x) {
int sum = 0;
while (x > 0) {
sum += Fentree[x];
x -= (x & (-x));
}
return sum;
}
// function to process the queries
vector<int> processingQueries(vector<int>& q, int m) {
vector<int> r, Fentree((2 * m) + 1, 0);
unordered_map<int, int> hm;
for (int x = 1; x <= m; ++x) {
hm[x] = x + m;
updateArray(Fentree, x + m, 1);
}
for (int que : q){
r.push_back(calSum(Fentree, hm[que]) - 1); //pushing element to the front
updateArray(Fentree, hm[que], -1);
updateArray(Fentree, m, 1);
hm[que] = m;
m--;
}
return r;
}
int main(){
vector<int> Q = { 4, 2, 2, 4}; // initializing Query array
int m = 5;
vector<int> result;
result = processingQueries(Q, m);
cout << "The indices after moving query element to the front are ";
for (int x = 0;x < result.size(); x++)
cout << result[x] << " ";
return 0;
}
輸出
The indices after moving query element to the front are 3 2 0 1
結論
我們已經完成了本教程關於應用範圍查詢以搜尋元素並將其推送到陣列前方的內容。我們使用了兩種方法來實現任務：用於搜尋的樸素方法和 Fenwick 樹。透過一些示例詳細說明了任務，以瞭解問題陳述的要求。使用了不同的 C++ 庫函式來實現問題陳述。
81 次瀏覽
