华为OD机试 - 推荐多样性（Java 2024 E卷 100分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
推荐多样性需要从多个列表中选择元素，一次性要返回 N 屏数据（窗口数量），每屏展示 K 个元素（窗口大小），选择策略:
各个列表元素需要做穿插处理，即先从第一个列表中为每屏选择一个元素，再从第二个列表中为每屏选择一个元素，依次类推。
每个列表的元素尽量均分为 N 份，如果不够 N 份，也要全部分配完，参考样例图：
(1) 从第一个列表中选择 4 条 0123，分别放到 4 个窗口中
(2) 从第二个列表中选择 4 条 10111213，分别放到 4 个窗口中
(3) 从第三个列表中选择 4 条 20212223，分别放到 4 个窗口中
(4) 再从第一个列表中选择 4 条 4567，分别放到 4 个窗口中
…
(5) 再从第一个列表中选择，由于数量不足 4 条，取剩下的 2 条，放到窗口1 和窗口2
(6) 再从第二个列表中选择，由于数量不足 4 条且总的元素数达到窗口要求，取 1819 放到窗口3 和窗口4
二、输入描述
第一行输入为 N，表示需要输出的窗口数量，取值范围 [1, 10]
第二行输入为 K，表示每个窗口需要的 元素数量，取值范围 [1, 100]
之后的行数不定（行数取值范围 [1, 10]），表示每个列表输出的元素列表。元素之间以空格隔开，已经过排序处理，每个列表输出的元素数量取值范围 [1, 100]
三、输出描述
输出元素列表，元素数量 = 窗口数量 * 窗口大小，元素之间以空格分隔，多个窗口合并为一个列表输出，参考样例：
先输出窗口1的元素列表，再输出窗口2的元素列表，再输出窗口3的元素列表，最后输出窗口4的元素列表。
备注
- 每个列表会保证元素数量满足窗口要求，不需要考虑元素不足情况
- 每个列表的元素已去重，不需要考虑元素重复情况
- 每个列表的元素列表均不为空，不需要考虑列表为空的情况
- 每个列表的元素列表已经过排序处理，输出结果要保证不改变同一个列表的元素顺序
- 每个列表的元素数量可能是不同的
四、测试用例
测试用例1：
1、输入
4
7
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
2、输出
0 10 20 4 14 24 8 1 11 21 5 15 25 9 2 12 22 6 16 26 18 3 13 23 7 17 27 19
3、说明
测试用例2：
1、输入
2
3
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
2、输出
0 10 20 1 11 21
3、说明
五、解题思路
1、问题分析
问题要求我们从多个排序好的列表中选择元素，以 “轮询” 的方式将元素分配到多个窗口中。每个窗口的展示数量固定，窗口数量也固定。主要目标是通过轮询方式选择元素，确保列表中的元素尽量平均分布到各个窗口中，同时保持列表中元素的顺序不变。
2、ArrayList + LinkedList
使用 ArrayList 存储每个输入列表，每个输入列表使用 LinkedList 来存储元素。
选择 LinkedList 的原因是它可以高效地在列表头部移除元素（removeFirst 操作的时间复杂度为 O(1)），这在轮询分配元素时非常重要。
3、具体步骤：
- 读取窗口数量 N 和每个窗口需要的元素数量 K。接着读取多个列表，每个列表包含已排序的整数。
- 使用一个二维列表来存储输入的每个列表。每个列表使用 LinkedList 以便于从列表头部快速删除元素。
- 创建一个一维数组 windows，大小为 N * K，用于存储所有窗口的元素。
- 使用一个指针 idx 表示当前正在分配元素的位置，以及一个指针 level 表示当前从哪个列表中取元素。
- 使用一个循环，直到所有窗口都填满：
- 对于每一轮分配，轮询当前列表，将其前 N 个元素依次分配给 N 个窗口。
- 如果当前列表的元素不够 N 个，或者被取空，则切换到下一个列表进行分配。
- 每轮次需要检查列表是否为空，如果为空则移除，以防止越界。
- 按照窗口的列顺序进行输出，将每个窗口的元素按列拼接成最终的结果。
主要使用了轮询遍历法。每次从当前列表中为每个窗口分配一个元素，然后切换到下一个列表。这样可以确保元素被均匀分布在各个窗口中。
4、时间复杂度
总时间复杂度为 O(N * K)，其中 N 是窗口数量，K 是每个窗口的元素数量。主要耗时在于分配元素和输出结果的过程中。
六、Java算法源码
public class OdTest04 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
int k = Integer.parseInt(sc.nextLine());
ArrayList<LinkedList<Integer>> lists = new ArrayList<>();
while (sc.hasNextLine()) {
String line = sc.nextLine();
// 本地测试，以空行作为输入截止条件
if (line.length() == 0) break;
Integer[] nums =
Arrays.stream(line.split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
lists.add(new LinkedList<>(Arrays.asList(nums)));
}
// 窗口矩阵，k行n列，每一列对应一个窗口，这里将二维矩阵一维化，方便后面赋值
int[] windows = new int[k * n];
// 窗口矩阵中正在赋值的索引位置
int idx = 0;
// 正在从第level个列表中取值
int level = 0;
// 当窗口矩阵填满后，结束循环
while (idx < windows.length) {
// 当前轮次是否发生了"借"动作
boolean flag = false;
// 从第level个列表中取前n个元素
for (int i = 0; i < n; i++) {
windows[idx++] = lists.get(level).removeFirst();
// 如果第level个列表没有元素了，则继续切到下一个列表中"借"
if (lists.get(level).size() == 0 && lists.size() > 1) {
lists.remove(level); // 删除空列表
level %= lists.size(); // 防止越界
flag = true; // 发生了"借"动作
}
}
// 如果没有发生"借"动作，则需要切到下一行
if (!flag) {
level = (level + 1) % lists.size(); // 防止越界
}
}
StringJoiner sj = new StringJoiner(" ");
// 遍历窗口矩阵的每一列
for (int j = 0; j < n; j++) { // 遍历列号
for (int i = 0; i < k; i++) { // 遍历行号
sj.add(windows[i * n + j] + ""); // 将每一列的元素进行拼接
}
}
System.out.println(sj);
}
}
七、效果展示
1、输入
5
5
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
2、输出
0 10 20 5 15 1 11 21 6 16 2 12 22 7 17 3 13 23 8 18 4 14 24 9 19
3、说明
🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）
🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
原文地址：https://blog.csdn.net/guorui_java/article/details/142282722
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！