原文:
给定一个由 n 个整数组成的数组 arr[] 和一个具有 q 个整数的数组查询[] ，任务是在将第一个出现的查询【i】移动到数组 arr[] 的末尾后，为范围【0，q】中的每个 i 打印数组 arr[]
示例:
输入: arr[] = {1，3，1，3}，查询[] = {3，1} 输出: 1 3 3 1 解释:在第一次迭代中，将查询[0]的第一次出现发送到末尾，即，将 3 的第一次出现发送到末尾。 因此，数组变成 arr[] = {1，1，3，3}。 在第二次迭代中，将查询[1]的第一次出现发送到最后。 因此，数组 arr[] = {1，3，3，1}是必需的数组。
输入: arr[] = {1，2，3，4，5}，查询[] = {4，3} 输出: 1 2 5 4 3
方法:给定的问题可以使用来解决。其思想是将每个整数的索引列表存储在中，对于当前整数的操作，从表示当前整数第一次出现的索引的集合中移除第一个索引，并将最后一个索引的索引插入到集合中。以下是要遵循的步骤:
- 创建一个 m ，存储每个索引的索引集。
- arr[] ，并将所有索引插入到地图 m 中各自的集合中。
- 使用变量 i 迭代数组查询[] ，并执行以下操作:
- 从集合m[查询[i]] 中移除代表第一个出现的第一个元素。
- 将最后一个元素的索引，即 n i 插入到集合 m【查询[i]】中。
- 按照最终索引的递增顺序打印元素，这是必需的答案。
下面是上述方法的实现:
c 14
// c program of the above approach
#include
using namespace std;
// function to print the array after
// performing the given operations
void sendtolast(vector arr,
vector query)
{
// stores index of present
// integers in a set
unordered_map > m;
// loop to insert indices
// into the given map
for (int i = 0; i < arr.size(); i ) {
m[arr[i]].insert(i);
}
// loop to iterate the
// query array
for (int i = 0; i < query.size(); i ) {
// erase the index of current
// element from the map
m[query[i]].erase(*m[query[i]].begin());
// insert new location
m[query[i]].insert(arr.size() i);
}
// vector of pair to store index
// value pair
vector > v;
// insert all index value pair
// into the vector v
for (auto x : m) {
for (auto y : x.second) {
v.push_back({ y, x.first });
}
}
// sort v in increasing order
// of the index
sort(v.begin(), v.end());
// print array
for (int i = 0; i < v.size(); i ) {
cout << v[i].second << " ";
}
}
// driver code
int main()
{
vector arr{ 1, 3, 1, 3 };
vector query{ 3, 1 };
sendtolast(arr, query);
return 0;
}
output
1 3 3 1
时间复杂度: o(q * log n) 辅助空间: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
