我在此行中使用std::vector：
std::vector<bool> visited(length);
要解决 LeetCode 问题：
给定一个整数数组 arr，您最初位于 数组的第一个索引。
在一个步骤中，您可以从索引 i 跳转到索引：
I + 1
- 其中：I + 1 <长度。>
i - 1- 其中：i - 1>= 0。
j 其中： arr[i]- == arr[j] and i ！= j.
返回到达 数组。
请注意，任何时候都不能跳出数组。
示例 1：
输入：arr = [100，-23，-23,404,100,23,23,23,3,404]
输出：3
说明：您需要从索引 0 --> 4 --> 3 --> 9 跳转三次。请注意，索引 9 是数组的最后一个索引。
约束：
1 <= 长度 <= 5 * 10^4 -10^8 <= arr[i] <= 10^8
#include <vector>
#include <unordered_map>
#include <queue>
class Solution {
public:
int minJumps(const std::vector<int>& nums) {
int length = nums.size();
std::unordered_map<int, std::vector<int>> value_indices;
for (int index = 0; index < length; index++) {
value_indices[nums[index]].push_back(index);
}
std::vector<bool> visited(length);
visited[0] = true;
std::queue<int> queue;
queue.push(0);
int min_steps = 0;
while (!queue.empty()) {
for (int size = queue.size(); size > 0; size--) {
int index = queue.front();
queue.pop();
if (index == length - 1) {
return min_steps;
}
std::vector<int>& next_jumps = value_indices[nums[index]];
next_jumps.push_back(index - 1);
next_jumps.push_back(index + 1);
for (int jump : next_jumps) {
if (jump > -1 && jump < length && !visited[jump]) {
visited[jump] = true;
queue.push(jump);
}
}
next_jumps.clear();
}
min_steps++;
}
return 0;
}
};
似乎std::array效率更高，但我不确定。我应该使用std::array吗，您建议如何这样做？还有什么可以使此解决方案更高效吗？
std::array只是一个花哨的C ++包装器，用于与普通C数组相同的对象。就像 C 数组一样，需要事先知道大小。如果在函数中分配了一个数组，它就像 C 数组一样进入堆栈。如果它作为类的一部分分配，则数组的存储是类开头的简单偏移量。
因此，如果您需要访问数组内存中的 a 单元，因为它很接近，因此很可能在缓存中。
std::vector具有动态存储，这意味着存储是在堆上分配的(使用new或类似(。因此，如果您正在堆栈上工作，则存储可能很远，并且更有可能不在缓存中，因此从这个意义上讲可能会更慢。
另一方面，您不需要知道std::vector会有多大。当矢量用完先前分配的存储空间时，它会将数据移动到更大的存储位置。因此，在添加时，为避免不断调整大小，您可以预先reserve空间以加快速度。
由于存储是非本地的，因此std::vector将比std::array更好地移动。std::array和std::vector将始终将数据连续存储在内存中，因此获取第 n 个元素可以在 O(1( 时间内完成。