提问人：beetard 提问时间：10/5/2023 最后编辑：fudobeetard 更新时间：10/6/2023 访问量：53
从原始列表中获取元素的索引和剩余元素的值
get the index of an element from the original list and the value of the remaining element
问：
我正在尝试解决一个 Josephus 问题，其中除了剩余元素的值外，我还需要在原始列表中返回其索引。我自己实现了列表，它运行良好，我正确地获得了值，但我无法弄清楚如何从原始数组中获取索引！
谁能向我解释一下？
我的代码：
#include "circular_linked_list.h"
enum class direction { clockwise, counterclockwise };
template<typename T>
std::pair<int, T> Josephus_problem(CircularLinkedList<T> list, direction dir, unsigned step) {
if (list.getLength() == 0) {
throw std::invalid_argument("List is empty");
}
int currentIndex = 0;
int size = list.getLength();
int finalIndex = 0;
while (list.getLength() > 1) {
if (dir == direction::counterclockwise) {
finalIndex -= step + 1;//???
currentIndex = (currentIndex - step + 1) % list.getLength();
} else {
finalIndex += step - 1;//???
currentIndex = (currentIndex + step - 1) % list.getLength();
}
list.removeAt(currentIndex);
}
finalIndex = ...;//Don't know what to do here!
return {finalIndex, list[0]};
}
答：
0赞
selbie
10/5/2023
#1
差不多是这样：
初始化无符号整数 （size_t） 的 std：：list，表示列表中从 0 到 N-1 的每个元素的索引。
std::list<size_t> listOfPositions;
size_t N = <how ever many elements are in your original list>
for (size_t i = 0; i < N; i++) {
listOfPositions.push_back(i);
}
然后，只需逐个遍历列表即可。每次点击第 STEPth 元素时，都会将其擦除。您可以利用这样一个事实，即 on a position 元素将返回 next item。list.erase
以下是简单的逻辑：
unsigned int index = 1;
auto pos = listOfPositions.begin();
while (listOfPositions.size() > 1) {
if (index == step) {
pos = listOfPositions.erase(pos); // returns the next item in the list
index = 1;
}
else {
pos++;
index++;
}
if (pos == listOfPositions.begin()) {
pos = listOfPositions.end();
}
}
您可以利用反向迭代器进行逆时针操作。对上述逻辑进行了一些小的调整，使其适用于反向迭代。
unsigned int index = 1;
auto pos = listOfPositions.rbegin() + N - 1; // point to the first item in the list
while (listOfPositions.size() > 1) {
if (index == step) {
pos = listOfPositions.erase(pos); // return the previous item in the list when using reverse iterators
index = 1;
}
else {
pos++;
index++;
}
if (pos == listOfPositions.rend()) {
pos = listOfPositions.rbegin();
}
}
在这两种情况下，“最后剩余的索引”是这样的：
size_t last_remaining = *pos;
评论
0赞
selbie
10/6/2023
我想到的另一件事。与其使用顺时针与逆时针循环的交替实现，不如反向初始化列表项，其中 0 仍然是第一项。而不是像逆时针那样初始化它。这样你就不需要迭代循环的 rbegin/rend 版本来求解了。0,1,2,3,4,5,60,6,5,4,3,2,1
评论
list.getLength()-1