在编程实践中，我们常会遇到需要按特定规则从一个集合中循环选取并移除元素的场景。一个经典的例子是“圆桌吃菜”问题：假设有 `numberOfDishes` 盘菜围成一圈，编号从 `1` 到 `numberOfDishes`。一个人想按照每 `everyDishNumberToEat` 盘菜吃一次的规则，直到吃完所有菜。我们的目标是确定这些菜被吃掉的顺序。
例如，如果有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] }}
运行结果：
简篇AI排版
AI排版工具，上传图文素材，秒出专业效果！
554 查看详情
numberOfDishes = 10, everyDishNumberToEat = 3Output: [3, 6, 9, 2, 7, 1, 8, 5, 10, 4]---numberOfDishes = 5, everyDishNumberToEat = 2Output: [2, 4, 1, 5, 3]---numberOfDishes = 7, everyDishNumberToEat = 1Output: [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免费学习笔记（深入）”；
以上就是Java实现：按指定步长重排列表元素的算法教程的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/312448.html
微信扫一扫 
支付宝扫一扫 
