循环步进移除元素实现列表重排方法

本文详细阐述了如何通过循环步进的方式，从一个动态列表中按特定规则移除元素并构建新的序列。核心方法是利用 `LinkedList` 的高效移除特性，结合模运算 (`%`) 精确计算每次移除的元素索引，以适应列表大小的动态变化和循环特性，直至所有元素被处理完毕。

问题描述

假设有一个圆桌，上面摆放着 numberOfDishes 份菜肴，从 1 到 numberOfDishes 依次编号。一个人想按照特定的规则品尝所有菜肴：他将从当前位置开始，每隔 everyDishNumberToEat - 1 份菜肴（即品尝第 everyDishNumberToEat 份）就品尝一份，直到所有菜肴都被品尝完毕。每次品尝后，该菜肴就会从圆桌上移除。我们需要确定菜肴被品尝的顺序。

示例：

• numberOfDishes = 10
• everyDishNumberToEat = 3
• 初始菜肴列表：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

期望输出的品尝顺序：[3, 6, 9, 2, 7, 1, 8, 5, 10, 4]

核心逻辑解析

解决此类问题的关键在于正确处理两个方面：动态列表的元素移除和循环索引的计算。

1. 动态列表的选择： 由于我们需要频繁地从列表中移除元素，且每次移除后列表的索引会发生变化，使用 java.util.LinkedList 是一个高效的选择。LinkedList 在头部或中间进行元素移除操作时，性能优于 ArrayList。

2. 循环索引计算： 这是问题的核心。每次品尝菜肴时，我们需要根据 everyDishNumberToEat 来确定下一个要移除的元素。由于列表是“圆桌”式的，且每次移除后列表大小会减小，我们需要使用模运算 (%) 来确保索引始终在当前列表的有效范围内，并实现循环查找。

   • 步长 (step) 的确定： 如果要品尝“每第 everyDishNumberToEat 份”菜肴，这意味着从当前位置跳过 everyDishNumberToEat - 1 份菜肴。因此，实际的步长 step 应该设置为 everyDishNumberToEat - 1。
   • 索引更新公式： 每次迭代，新的索引 i 应根据当前索引、步长和当前列表大小来计算： i = (i + step) % dishes.size(); 这个公式确保了：
     • i + step 实现了步进。
     • % dishes.size() 实现了“圆桌”的循环特性，即使 i + step 超出了当前列表的末尾，也能回到列表的开头。
     • 每次 dishes.size() 都会减小，模运算能够自适应地调整索引范围。

3. 循环终止条件： 品尝过程应持续进行，直到所有菜肴都被品尝完毕。因此，一个 while (!dishes.isEmpty()) 循环是合适的，它会一直执行直到 dishes 列表为空。

实现步骤

1. 初始化列表： 创建一个 LinkedList 来存储初始的菜肴编号，从 1 到 numberOfDishes。同时，创建一个 ArrayList 来存储最终的品尝顺序。
2. 设置步长： 计算实际的步长 step = everyDishNumberToEat - 1。
3. 循环品尝： 使用 while 循环，只要菜肴列表不为空，就执行以下操作：
   • 根据公式 i = (i + step) % dishes.size(); 更新当前要移除的菜肴的索引 i。
   • 从 dishes 列表中移除位于索引 i 的菜肴，并将其添加到结果列表中。
4. 返回结果： 循环结束后，返回存储品尝顺序的结果列表。

示例代码

以下是基于上述逻辑的 Java 实现：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class DishOrderDeterminer {

    /**
     * 根据特定规则确定菜肴的品尝顺序。
     *
     * @param numberOfDishes        菜肴的总数量。
     * @param everyDishNumberToEat  每次品尝的步长（例如，3 表示每第3份）。
     * @return 菜肴被品尝的顺序列表。
     */
    public static List determineDishOrder(int numberOfDishes, int everyDishNumberToEat) {
        // 使用 LinkedList 存储待品尝的菜肴，因为它在中间移除元素效率较高。
        List dishes = new LinkedList<>();
        // 使用 ArrayList 存储品尝的顺序。
        List result = new ArrayList<>();

        // 初始化菜肴列表，编号从 1 到 numberOfDishes。
        for (int i = 1; i <= numberOfDishes; i++) {
            dishes.add(i);
        }

        // 计算实际的步长。如果每 everyDishNumberToEat 份品尝一次，
        // 那么从当前位置需要跳过 everyDishNumberToEat - 1 个位置。
        int step = everyDishNumberToEat - 1;
        // 当前要移除的元素的索引，初始为 0。
        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
        int numberOfDishes1 = 10;
        int everyDishNumberToEat1 = 3;
        System.out.println("Input: numberOfDishes = " + numberOfDishes1 + ", everyDishNumberToEat = " + everyDishNumberToEat1);
        System.out.println("Output: " + determineDishOrder(numberOfDishes1, everyDishNumberToEat1)); // 期望: [3, 6, 9, 2, 7, 1, 8, 5, 10, 4]

        System.out.println("---");

        // 示例 2
        int numberOfDishes2 = 5;
        int everyDishNumberToEat2 = 2;
        System.out.println("Input: numberOfDishes = " + numberOfDishes2 + ", everyDishNumberToEat = " + everyDishNumberToEat2);
        System.out.println("Output: " + determineDishOrder(numberOfDishes2, everyDishNumberToEat2)); // 期望: [2, 4, 1, 5, 3]
    }
}

运行结果：

Input: numberOfDishes = 10, everyDishNumberToEat = 3
Output: [3, 6, 9, 2, 7, 1, 8, 5, 10, 4]
---
Input: numberOfDishes = 5, everyDishNumberToEat = 2
Output: [2, 4, 1, 5, 3]

注意事项与总结

• 数据结构选择： LinkedList 在频繁的中间元素移除操作上表现更优，而 ArrayList 在随机访问上更优。对于本问题，LinkedList 是更合适的选择。
• 索引的动态性： 务必理解 currentIndex = (currentIndex + step) % dishes.size(); 这行代码的含义。它不仅处理了循环性，还适应了列表因元素移除而不断减小的大小。
• 步长计算： everyDishNumberToEat 是指“第 N 份”，而索引是从 0 开始的，并且是相对于当前位置的“跳过”数量。因此，步长应为 everyDishNumberToEat - 1。
• 循环条件： 使用 while (!dishes.isEmpty()) 确保所有元素都被处理，而不是固定次数的 for 循环，因为列表大小在变化。

通过掌握上述核心逻辑和实现细节，可以有效地解决这类基于循环步进和动态列表移除的问题。