我有一项任务,要求我为所有数组条目找到数组中所有较大元素中的最小元素,并将相应的索引存储在数组中,但我无法完全弄清楚解决方案的最后部分。
这与此处解释的问题有点相似: https://www.geeksforgeeks.org/smallest-greater-elements-in-whole-array/
唯一的区别是仅考虑数组条目右侧的值 (j>i),例如:
input: [80; 19; 49; 45; 65; 71; 76; 28; 68; 66]
output: [-1; 7; 4; 4; 9; 6; -1; 9; -1; -1]
自平衡树的解决方案对我来说很有意义。但是,我仍然需要考虑索引,因为只有数组条目右侧的解决方案才有效。
有没有办法将插入值的索引映射到树条目,或者创建具有相同结构的第二棵树,但旧数组条目的索引而不是实际值作为节点?我不确定,因为自平衡树的结构当然取决于插入的值(较大的值右子树,较小的值左子树)。
编辑:实际上第二个 AVL 树可能不会有帮助,因为我必须检查索引是否更大并且在遍历树时数组条目更大......
最简单的解决方案是从右到左迭代输入,对于每个元素在树(或任何具有 O(LogN) 查找和插入的数据结构)中查找第一个更大的元素,然后添加该元素到树上。这样,较大的元素总是出现在输入中的元素之后。
对于 C++ 版本,您可以使用
std::map
,其中元素的值是键,元素在输入中的索引是值,并使用 upper_bound
获取下一个更大的值:
#include <iostream>
#include <vector>
#include <map>
void nextValues(std::vector<int> &in, std::vector<int> &out) {
std::map<int, int> tree;
for (int i = in.size() - 1; i >= 0; i--) {
out.insert(out.begin(), tree.upper_bound(in[i])->second - 1);
tree.insert(std::pair<int, int>(in[i], i + 1));
}
}
int main() {
std::vector<int> a = {80,19,49,45,65,71,76,28,68,66};
std::vector<int> b;
nextValues(a, b);
for (int i : b) std::cout << (int) i << ","; // -1,7,4,4,9,6,-1,9,-1,-1
return 0;
}
你可以用与极客对极客文章相同的逻辑来解决它:
vector<int> findLeastGreater(vector<int>& arr, int n) {
// similar to Smallest greater elements in whole array
// except, add to set from last element to first
// after each addition to set, find it+1 for each array index
vector<int> res(n, -1);
set<int> s;
s.insert(arr[n-1]);
for (int i = n-2; i >= 0; i--) {
int curr = arr[i];
s.insert(curr);
auto it = s.find(curr);
it++;
if (it != s.end()) {
res[i] = *it;
}
}
return res;
}