C++求解数组各元素最近最小与最大数之和并保留原索引问题
问题原因
你之前的实现思路逻辑本身是对的,错误点在于排序过程中丢失了元素数值和原数组索引的对应关系,导致计算得到的和无法回填到结果数组的正确位置,最终出现索引错位。
解决思路
- 先将原数组的每个元素和它对应的原始索引绑定为一组数据,再进行排序,保留索引映射关系
- 遍历排序后的数组,按规则计算每个元素的「最近更小值 + 最近更大值」的和
- 按照绑定的原始索引,把计算得到的和写入结果数组的对应位置,保证索引一致
C++ 实现代码
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> calcNearestSum(const vector<int>& arr) { int n = arr.size(); // 绑定每个元素的数值和对应的原数组索引 vector<pair<int, int>> valWithIdx; for (int i = 0; i < n; ++i) { valWithIdx.emplace_back(arr[i], i); } // 按元素数值从小到大排序 sort(valWithIdx.begin(), valWithIdx.end()); vector<int> res(n); for (int i = 0; i < n; ++i) { // 计算最近更小值,首元素无更小值取0 int nearestMin = i == 0 ? 0 : valWithIdx[i-1].first; // 计算最近更大值,尾元素无更大值取0 int nearestMax = i == n-1 ? 0 : valWithIdx[i+1].first; // 把和写入原索引对应的位置 res[valWithIdx[i].second] = nearestMin + nearestMax; } return res; } // 测试示例 int main() { vector<int> input = {1,5,2,3,8}; vector<int> output = calcNearestSum(input); // 输出结果:2 11 4 7 5 for (int num : output) { cout << num << " "; } return 0; }
上述代码运行后输出结果和你给出的预期完全一致。
内容的提问来源于stack exchange,提问作者Kunal Chaudhary
相关产品推荐
相关产品推荐

