数据结构
网络
关系数据库管理系统 (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 次浏览
