豆包MarsCode：构造特定数组的逆序拼接

问题描述

---

思路分析

1. 数组的组成：

• 我们要根据 i 的不同值拼接出不同长度的子数组。
• 对于每个 i 从 1 到 n，我们要把数字从 n 逆序到 i 拼接成一个子数组。
  • 例如，当 i = 1 时，拼接 [n, n-1, ..., 1]。
  • 当 i = 2 时，拼接 [n, n-1, ..., 2]。
  • 一直到 i = n，拼接的数组只有 [n]。

2. 数组的拼接顺序：

• 每次拼接的数组要依次放入最终结果数组中。因此，我们需要有一个结果数组来保存这些拼接后的数组。

3. 计算结果数组的长度：

• 每个子数组的长度是由当前 i 决定的。对于 i = 1，拼接的是 n 到 1，长度为 n；对于 i = 2，拼接的是 n 到 2，长度为 n-1；依此类推，直到 i = n，拼接的数组长度为 1。

• 因此，总长度就是：

  $\text{totalLength}=n+(n-1)+(n-2)+...+1=\frac{n(n+1)}{2}$

  显而易见这是一个等差数列的求和公式。

4. 实现步骤：

• 第一步，计算最终数组的总长度（totalLength）。
• 第二步，创建一个大小为 totalLength 的结果数组。
• 第三步，使用两层循环：
  • 外层循环遍历 i 从 1 到 n。
  • 内层循环从 n 逆序填充到当前的 i。
• 最后，返回这个结果数组。

---

参考代码（Java）

import java.util.Arrays;

public class Main {
    public static int[] solution(int n) {
        // 先计算出数组的总长度
        int totalLength = 0;
        for (int i = 1; i <= n; i++) {
            totalLength += (n - i + 1);
        }

        // 创建一个结果数组
        int[] result = new int[totalLength];
        int index = 0;

        // 按照规则填充结果数组
        for (int i = 1; i <= n; i++) {
            // 填充当前的部分 [n, n-1, ..., i]
            for (int j = n; j >= i; j--) {
                result[index++] = j;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.equals(solution(3), new int[]{3, 2, 1, 3, 2, 3}));
        System.out.println(Arrays.equals(solution(4), new int[]{4, 3, 2, 1, 4, 3, 2, 4, 3, 4}));
        System.out.println(Arrays.equals(solution(5), new int[]{5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5}));
    }
}

代码分析

1. 计算数组总长度

int totalLength = 0;
for (int i = 1; i <= n; i++) {
    totalLength += (n - i + 1);
}

• 在这个部分，代码通过一个循环来计算最终结果数组的总长度。
• 对于每个 i 从 1 到 n，我们需要拼接一个长度为 (n - i + 1) 的子数组。例如：
  • 当 i = 1 时，长度是 n（拼接 [n, n-1, ..., 1]）。
  • 当 i = 2 时，长度是 n - 1（拼接 [n, n-1, ..., 2]）。
  • 一直到 i = n 时，长度是 1（拼接 [n]）。
• 将每个长度累加，最终得出结果数组的总长度。

2. 创建结果数组

int[] result = new int[totalLength];
int index = 0;

• 根据计算得到的 totalLength 创建一个新的整数数组 result，用来存储最终拼接的结果。
• 使用 index 来跟踪我们在 result 数组中的位置。每次填充一个元素时，index 会增加。

3. 填充结果数组

for (int i = 1; i <= n; i++) {
    // 填充当前的部分 [n, n-1, ..., i]
    for (int j = n; j >= i; j--) {
        result[index++] = j;
    }
}

• 外层循环：i 从 1 遍历到 n，代表我们要填充的每个子数组的起始位置。
• 内层循环：对于每个 i，从 n 到 i 逆序填充结果数组。内层循环的次数由 i 决定：
  • 对于 i = 1，内层循环会填充 n, n-1, ..., 1。
  • 对于 i = 2，内层循环会填充 n, n-1, ..., 2。
  • 直到 i = n，只填充 n。
• 每次填充一个数字时，index 会增加，确保结果数组按顺序填充。

4. 返回结果

return result;

• 完成数组的填充后，返回这个 result 数组。

总结：

• 核心逻辑：通过两层循环实现从 n 到 i 的逆序拼接。
• 时间复杂度：$O(n^2)$，因为内外循环的嵌套导致操作次数随着 $n$ 增加而呈二次增长。
• 空间复杂度：$O(n^2)$，因为我们创建了一个长度为 $n(n+1)/2$ 的数组来保存结果。

原文地址：https://blog.csdn.net/2302_79730293/article/details/145233373

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！