例如，如果有10盘菜（编号1到10），每3盘吃一次： 输入： numberOfDishes = 10everyDishNumberToEat = 3 初始菜品列表：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
输出： [3, 6, 9, 2, 7, 1, 8, 5, 10, 4]
这本质上是一个约瑟夫环问题的变种，需要我们精确计算每次移除的元素索引。
核心算法思路
要解决这个问题，我们需要模拟一个循环过程，每次从当前剩余的菜品列表中移除一个元素，并更新下一次移除的起始位置。以下是实现这一逻辑的关键点：
数据结构选择： 由于我们需要频繁地从列表的任意位置移除元素，LinkedList 是一个比 ArrayList 更高效的选择。LinkedList 在中间插入或删除元素的平均时间复杂度为 O(1)，而 ArrayList 则为 O(n)，因为需要移动后续所有元素。
步长计算： 题目中“每 everyDishNumberToEat 盘菜”指的是从当前位置开始数第 everyDishNumberToEat 个元素。由于列表索引通常从0开始，如果 everyDishNumberToEat 为1，则表示移除当前位置的元素；如果为3，则表示移除当前位置往后数2个位置的元素（即索引为 current_index + (3-1) 的元素）。因此，实际的步长 step 应该计算为 everyDishNumberToEat - 1。
-
循环索引与模运算： 当我们在一个不断缩小的列表中循环选择元素时，需要确保索引不会超出当前列表的边界。模运算（%）在这里发挥了关键作用。每次计算新的移除索引时，我们应该将当前索引加上步长，然后对当前列表的长度取模。 新的索引 i = (i + step) % dishes.size() 这样做可以保证：
- 即使 i + step 超过了 dishes.size()，索引也会“绕回”列表的开头。
- 每次移除一个元素后，dishes.size() 会减小，模运算能够动态适应列表长度的变化。
循环终止条件： 我们需要一直循环，直到所有的菜都被吃完，即原始列表变为空。因此，while (!dishes.isEmpty()) 是合适的循环条件。
示例代码实现
下面是基于上述思路的Java实现：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class DishOrderDeterminer {
/**
* 根据指定步长重排列表元素，模拟圆桌吃菜问题。
*
* @param numberOfDishes 菜品总数
* @param everyDishNumberToEat 每次跳过的盘数（从当前位置开始数第几盘）
* @return 菜品被吃掉的顺序列表
*/
public static List determineDishOrder(int numberOfDishes, int everyDishNumberToEat) {
// 使用LinkedList存储菜品，方便高效地移除元素
List dishes = new LinkedList<>();
// 存储菜品被吃掉的顺序
List result = new ArrayList<>();
// 初始化菜品列表，编号从1到numberOfDishes
for (int i = 1; i <= numberOfDishes; i++) {
dishes.add(i);
}
// 计算实际的步长。例如，如果每3盘吃一次，实际是跳过2个元素，然后吃第3个。
// 对于0-indexed的列表，这意味着索引需要移动 everyDishNumberToEat - 1 步。
int step = everyDishNumberToEat - 1;
// 当前移除元素的起始索引
int currentIndex = 0;
// 当菜品列表不为空时，持续移除元素
while (!dishes.isEmpty()) {
// 计算下一个要移除元素的索引
// currentIndex + step 实现了步长移动
// % dishes.size() 实现了循环回到列表开头，并适应列表长度的动态变化
currentIndex = (currentIndex + step) % dishes.size();
// 移除当前索引处的菜品
int eatenDish = dishes.remove(currentIndex);
// 将被吃掉的菜品添加到结果列表
result.add(eatenDish);
}
return result;
}
public static void main(String[] args) {
// 测试用例1: 10盘菜，每3盘吃一次
System.out.println("numberOfDishes = 10, everyDishNumberToEat = 3");
System.out.println("Output: " + determineDishOrder(10, 3)); // 预期: [3, 6, 9, 2, 7, 1, 8, 5, 10, 4]
System.out.println("\n---");
// 测试用例2: 5盘菜，每2盘吃一次
System.out.println("numberOfDishes = 5, everyDishNumberToEat = 2");
System.out.println("Output: " + determineDishOrder(5, 2)); // 预期: [2, 4, 1, 5, 3]
System.out.println("\n---");
// 测试用例3: 7盘菜，每1盘吃一次 (按顺序吃)
System.out.println("numberOfDishes = 7, everyDishNumberToEat = 1");
System.out.println("Output: " + determineDishOrder(7, 1)); // 预期: [1, 2, 3, 4, 5, 6, 7]
}
} 运行结果：
numberOfDishes = 10, everyDishNumberToEat = 3 Output: [3, 6, 9, 2, 7, 1, 8, 5, 10, 4] --- numberOfDishes = 5, everyDishNumberToEat = 2 Output: [2, 4, 1, 5, 3] --- numberOfDishes = 7, everyDishNumberToEat = 1 Output: [1, 2, 3, 4, 5, 6, 7]
关键概念与注意事项
- 索引 currentIndex 的更新： 每次移除元素后，LinkedList 的长度会减小，但 currentIndex 不会自动调整。模运算 currentIndex = (currentIndex + step) % dishes.size(); 确保了即使列表长度变化，currentIndex 也能正确地在新的列表范围内循环。
- everyDishNumberToEat - 1 的重要性： 题目中的“第 N 盘”通常是基于1的计数，而编程中的列表索引是基于0的。因此，将 everyDishNumberToEat 转换为0-indexed的步长，需要减去1。
- LinkedList 的性能优势： 在这种频繁进行中间元素删除的场景下，LinkedList 的 remove(index) 方法性能优于 ArrayList。ArrayList 的 remove(index) 需要将 index 之后的所有元素向前移动一位，时间复杂度为 O(n)。而 LinkedList 虽然查找指定索引的元素需要 O(n)，但一旦找到节点，删除操作是 O(1)。在实际应用中，由于我们每次都从 currentIndex 移动 step 步，通常不会从列表头部或尾部删除，因此 LinkedList 更为适合。
- 时间复杂度： 假设有 N 个元素。每次循环，我们都需要计算 currentIndex 并从 LinkedList 中移除一个元素。LinkedList 的 remove(index) 操作平均需要 O(N) 的时间来遍历到 index 位置（最坏情况），然后进行 O(1) 的删除。总共有 N 次移除操作，所以整体时间复杂度为 O(N^2)。对于大规模数据，可能需要考虑更优化的算法（例如使用Fenwick树或线段树），但这超出了本教程的范围。
总结
通过本教程，我们学习了如何使用Java解决一个经典的列表元素循环重排问题。核心在于理解模运算在循环索引计算中的作用，以及选择合适的数据结构（如 LinkedList）来优化频繁的中间元素删除操作。这种方法不仅适用于“圆桌吃菜”问题，也可以推广到其他需要按步长从动态集合中选取元素的场景。
立即学习“Java免费学习笔记（深入）”；
