华为OD机试真题——最小循环子数组 （2025B卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

2025-11-26 19:55:45 分类：golang 热度：16 评论： 0

2025 B卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《最小循环子数组》：

文章快捷目录

题目描述及说明

Java

python

JavaScript

C++

C

GO

题目名称：最小循环子数组

知识点：字符串匹配、KMP算法（或枚举验证）
时间限制：1秒
空间限制：256MB
限定语言：不限

题目描述

给定一个由若干整数组成的数组 nums，请检查数组是否是由某个子数组重复循环拼接而成，并输出这个最小的子数组。

输入描述：

  • 第一行输入数组中元素个数 n，1 ≤ n ≤ 100000。
  • 第二行输入数组的数字序列 nums，以空格分割，0 ≤ nums[i] ≤ 10。

输出描述：
输出最小的子数组的数字序列，以空格分割。

备注：
数组本身是其最大的子数组，循环1次可生成自身。

示例：
输入：

9  
1 2 1 1 2 1 1 2 1

输出：

1 2 1

说明：数组 [1,2,1,1,2,1,1,2,1] 可由子数组 [1,2,1] 重复循环3次拼接而成。

Java

问题分析

我们需要找到一个数组的最小循环子数组，即该数组可以由该子数组重复拼接而成。解决此问题的关键在于确定数组是否由某个子数组重复构成，并找出最小的这样的子数组。

解题思路

  1. 候选子数组长度的确定：循环子数组的长度必须是原数组长度的因数。
  2. 因数枚举：找出原数组长度的所有因数，并按从小到大顺序检查。
  3. 循环验证：对于每个候选长度，验证数组是否可以由该长度的子数组重复构成。
  4. 输出结果：找到第一个满足条件的最小子数组。

代码实现

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取数组长度
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt(); // 读取数组元素
        }

        // 生成所有可能的因数（包括n）
        TreeSet<Integer> factors = new TreeSet<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                factors.add(i);
                factors.add(n / i);
            }
        }

        // 遍历所有因数，从小到大检查
        for (int d : factors) {
            if (check(nums, d)) { // 验证当前因数对应的子数组是否符合循环条件
                printResult(nums, d); // 打印结果
                return;
            }
        }

        printResult(nums, n); // 最终必能匹配自身（d=n）
    }

    private static boolean check(int[] nums, int d) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[i % d]) { // 核心验证逻辑：每个位置必须与子数组对应位置相同
                return false;
            }
        }
        return true;
    }

    private static void printResult(int[] nums, int d) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < d; i++) {
            sb.append(nums[i]);
            if (i != d - 1) {
                sb.append(" ");
            }
        }
        System.out.println(sb);
    }
}

代码解析

  1. 输入处理

    int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
    nums[i] = scanner.nextInt();
}
    • 读取数组长度和元素。

  2. 因数生成

    TreeSet<Integer> factors = new TreeSet<>();
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        factors.add(i);
        factors.add(n / i);
    }
}
    • 遍历1到sqrt(n)，收集所有因数并存入有序集合，自动去重并排序。

  3. 循环验证

    for (int d : factors) {
    if (check(nums, d)) {
        printResult(nums, d);
        return;
    }
}
    • 从小到大遍历因数，验证每个因数对应的子数组是否符合循环条件。

  4. 验证逻辑

    private static boolean check(int[] nums, int d) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != nums[i % d]) {
            return false;
        }
    }
    return true;
}
    • 核心逻辑：数组的每个元素必须等于其对应子数组位置的元素。

  5. 结果输出

    private static void printResult(int[] nums, int d) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < d; i++) {
        sb.append(nums[i]);
        if (i != d - 1) {
            sb.append(" ");
        }
    }
    System.out.println(sb);
}
    • 输出最小循环子数组的前d个元素。

示例测试

  1. 输入示例1
    输入：

    9  
1 2 1 1 2 1 1 2 1

    输出：

    1 2 1

    解析：数组可由[1,2,1]重复3次构成。

  2. 输入示例2
    输入：

    6  
1 2 1 2 1 2

    输出：

    1 2

    解析：数组可由[1,2]重复3次构成。

  3. 输入示例3
    输入：

    5  
1 2 3 4 5

    输出：

    1 2 3 4 5

    解析：无更小的循环子数组，输出自身。

综合分析

  1. 时间复杂度

    • 因数生成：O(sqrt(n))，遍历到sqrt(n)即可收集所有因数。
    • 循环验证：最坏情况O(n log n)，每个因数的验证需O(n)，因数数量为O(log n)。

  2. 空间复杂度

    • O(n)，存储数组和因数集合。

  3. 正确性保证

    • 因数从小到大遍历确保找到最小解，验证逻辑严格匹配循环条件。

  4. 优势

    • 利用因数枚举和严格验证，保证高效性和正确性。
    • 代码简洁，逻辑清晰，覆盖所有边界情况（例如数组本身为解）。

python

问题分析

我们需要找到数组的最小循环子数组，即该数组可以由该子数组重复拼接而成。关键在于确定数组是否由某个子数组重复构成，并找出最小的这样的子数组。

解题思路

  1. KMP前缀函数：利用KMP算法中的前缀函数来找到最长公共前后缀，从而计算出可能的循环节长度。
  2. 循环节验证：通过计算得到的循环节长度，验证该长度是否能整除数组长度，从而确定最小循环子数组。
  3. 输出结果：若存在有效的循环节，输出对应子数组；否则输出原数组。

代码实现

n = int(input())
nums = list(map(int, input().split()))

def ***pute_prefix_function(arr):
    n = len(arr)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i-1]
        while j > 0 and arr[i] != arr[j]:
            j = pi[j-1]
        if arr[i] == arr[j]:
            j += 1
        pi[i] = j
    return pi

if n == 0:
    print()
else:
    pi = ***pute_prefix_function(nums)
    d_candidate = n - pi[-1]
    if d_candidate != 0 and n % d_candidate == 0:
        print(' '.join(map(str, nums[:d_candidate])))
    else:
        print(' '.join(map(str, nums)))

代码解析

  1. 输入处理

    n = int(input())
nums = list(map(int, input().split()))
    • 读取数组长度 n 和数组元素 nums。

  2. 前缀函数计算

    def ***pute_prefix_function(arr):
    n = len(arr)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i-1]  # 前一个字符的最长公共前后缀长度
        while j > 0 and arr[i] != arr[j]:
            j = pi[j-1]  # 回溯到更短的公共前后缀
        if arr[i] == arr[j]:
            j += 1  # 延长公共前后缀
        pi[i] = j
    return pi
    • 计算前缀函数数组 pi，其中 pi[i] 表示子数组 arr[0..i] 的最长公共前后缀长度。

  3. 候选循环节计算

    d_candidate = n - pi[-1]
    • 候选循环节长度 d_candidate = 数组长度 - 最长公共前后缀长度。

  4. 循环节验证

    if d_candidate != 0 and n % d_candidate == 0:
    print(' '.join(map(str, nums[:d_candidate])))
else:
    print(' '.join(map(str, nums)))
    • 若候选长度有效且能整除数组长度，输出对应的最小子数组；否则输出原数组。

示例测试

  1. 输入示例1
    输入：

    9  
1 2 1 1 2 1 1 2 1

    输出：
    1 2 1
    解析：前缀函数计算得最长公共前后缀长度为6，候选长度3，输出前3个元素。

  2. 输入示例2
    输入：

    6  
1 2 1 2 1 2

    输出：
    1 2
    解析：前缀函数计算得最长公共前后缀长度为4，候选长度2，输出前2个元素。

  3. 输入示例3
    输入：

    5  
1 2 3 4 5

    输出：
    1 2 3 4 5
    解析：候选长度5，无法有效循环，输出原数组。

综合分析

  1. 时间复杂度

    • 前缀函数计算：O(n)，遍历数组一次。
    • 候选验证：O(1)，直接数学运算。

  2. 空间复杂度

    • O(n)，存储前缀函数数组。

  3. 正确性保证

    • 前缀函数确保找到最长公共前后缀，从而推导出最小循环节长度。

  4. 优势

    • 时间复杂度严格为 O(n)，高效处理大规模输入。
    • 数学推导确保结果正确性，无需暴力枚举。

JavaScript

问题分析

我们需要找到数组的最小循环子数组，即该数组由其重复拼接而成。核心是通过前缀函数（KMP算法中的概念）确定可能的循环节长度。

解题思路

  1. 输入处理：读取数组长度 n 和数组元素。
  2. 前缀函数计算：生成前缀数组 pi，其中 pi[i] 表示子数组 nums[0..i] 的最长公共前后缀长度。
  3. 循环节推导：候选循环节长度 d = n - pi[n-1]。
  4. 循环节验证：若 d 能整除 n，则输出前 d 个元素；否则输出原数组。

代码实现

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line.trim());
});

rl.on('close', () => {
    const n = parseInt(lines[0]);
    if (lines.length < 2) {
        console.log(''); // 处理空输入
        return;
    }
    const nums = lines[1].split(' ').map(Number);
    
    // 计算前缀函数数组
    const ***putePrefix = (arr) => {
        const n = arr.length;
        const pi = new Array(n).fill(0);
        for (let i = 1; i < n; i++) {
            let j = pi[i - 1];
            while (j > 0 && arr[i] !== arr[j]) {
                j = pi[j - 1]; // 回溯到更短的公共前后缀
            }
            if (arr[i] === arr[j]) {
                j++;
            }
            pi[i] = j;
        }
        return pi;
    };

    if (n === 0) {
        console.log('');
        return;
    }

    const pi = ***putePrefix(nums);
    const d = n - pi[n - 1]; // 候选循环节长度

    // 验证循环节是否有效
    if (d !== 0 && n % d === 0) {
        console.log(nums.slice(0, d).join(' '));
    } else {
        console.log(nums.join(' '));
    }
});

代码解析

  1. 输入读取

    const rl = readline.createInterface(...);
rl.on('line', ...);
rl.on('close', ...);
    • 读取输入行并存储到 lines 数组。

  2. 输入解析

    const n = parseInt(lines[0]);
const nums = lines[1].split(' ').map(Number);
    • 读取数组长度 n 和元素数组 nums。

  3. 前缀函数计算

    const ***putePrefix = (arr) => {
    const pi = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        let j = pi[i - 1];
        while (j > 0 && arr[i] !== arr[j]) {
            j = pi[j - 1]; // 根据前缀数组回溯
        }
        if (arr[i] === arr[j]) j++;
        pi[i] = j;
    }
    return pi;
};
    • 遍历数组，计算每个位置的最长公共前后缀长度。

  4. 循环节推导与验证

    const d = n - pi[n - 1];
if (d !== 0 && n % d === 0) {
    console.log(nums.slice(0, d).join(' '));
} else {
    console.log(nums.join(' '));
}
    • 若候选长度 d 有效（能整除 n），输出前 d 个元素；否则输出原数组。

示例测试

  1. 输入示例1
    输入：

    9  
1 2 1 1 2 1 1 2 1

    输出：
    1 2 1
    解析：前缀数组末尾为6，d=9-6=3，输出前3个元素。

  2. 输入示例2
    输入：

    6  
1 2 1 2 1 2

    输出：
    1 2
    解析：前缀数组末尾为4，d=6-4=2，输出前2个元素。

  3. 输入示例3
    输入：

    5  
1 2 3 4 5

    输出：
    1 2 3 4 5
    解析：无法找到更小的循环节，输出原数组。

综合分析

维度 说明
时间复杂度 O(n)，计算前缀数组的时间复杂度为线性。
空间复杂度 O(n)，存储前缀数组和输入数组。
正确性 基于KMP算法的数学推导，严格匹配循环节条件。
优势 快速高效，无需暴力枚举，直接通过数学性质推导结果。
适用场景 需要快速找出字符串或数组的最小循环节的场景，如数据压缩、模式匹配等。

C++

问题分析

我们需要找到数组的最小循环子数组。核心思路是利用KMP算法中的前缀函数确定可能的循环节长度，从而快速找到最小循环子数组。

解题思路

  1. 前缀函数计算：生成前缀数组 pi，其中 pi[i] 表示子数组 nums[0..i] 的最长公共前后缀长度。
  2. 循环节推导：候选循环节长度 d = n - pi[n-1]。
  3. 循环节验证：若 d 能整除数组长度 n，则输出前 d 个元素；否则输出原数组。

代码实现

#include <iostream>
#include <vector>
using namespace std;

vector<int> ***putePrefix(const vector<int>& nums) {
    int n = nums.size();
    vector<int> pi(n, 0); // 前缀函数数组
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1]; // 前一位的最长公共前后缀长度
        while (j > 0 && nums[i] != nums[j]) { // 回溯到更短的公共前后缀
            j = pi[j - 1];
        }
        if (nums[i] == nums[j]) { // 匹配成功，长度+1
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

int main() {
    ios::sync_with_stdio(false); // 加速输入输出
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    vector<int> pi = ***putePrefix(nums);
    int d = n - pi.back(); // 循环节候选长度
    
    if (d != 0 && n % d == 0) { // 验证候选长度
        for (int i = 0; i < d; ++i) {
            if (i > 0) cout << " ";
            cout << nums[i];
        }
    } else { // 无法构成循环节，输出原数组
        for (int i = 0; i < n; ++i) {
            if (i > 0) cout << " ";
            cout << nums[i];
        }
    }
    cout << endl;
    
    return 0;
}

代码解析

  1. 前缀函数计算

    vector<int> ***putePrefix(const vector<int>& nums) {
    int n = nums.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1]; // 前一个字符的最长公共前后缀长度
        while (j > 0 && nums[i] != nums[j]) { // 回溯到更短的公共前后缀
            j = pi[j - 1];
        }
        if (nums[i] == nums[j]) { // 匹配成功，延长公共前后缀
            j++;
        }
        pi[i] = j;
    }
    return pi;
}
    • 计算前缀函数数组 pi，其中 pi[i] 表示子数组 nums[0..i] 的最长公共前后缀长度。

  2. 候选循环节长度计算

    int d = n - pi.back();
    • 通过前缀函数最后一个值推导候选循环节长度 d。

  3. 循环节验证与输出

    if (d != 0 && n % d == 0) {
    for (int i = 0; i < d; ++i) { ... } // 输出前d个元素
} else {
    for (int i = 0; i < n; ++i) { ... } // 输出原数组
}
    • 若候选长度有效（能整除 n），输出前 d 个元素；否则输出原数组。

示例测试

  1. 输入示例1
    输入：

    9  
1 2 1 1 2 1 1 2 1

    输出：
    1 2 1
    解析：前缀函数末尾值为6，d=3，数组可被分割为3个[1,2,1]。

  2. 输入示例2
    输入：

    6  
1 2 1 2 1 2

    输出：
    1 2
    解析：前缀函数末尾值为4，d=2，数组可被分割为3个[1,2]。

  3. 输入示例3
    输入：

    5  
1 2 3 4 5

    输出：
    1 2 3 4 5
    解析：前缀函数末尾值为0，d=5，无法分割成更小循环节。

综合分析

维度 说明
时间复杂度 O(n)，计算前缀函数仅需一次遍历。
空间复杂度 O(n)，存储前缀函数数组和输入数组。
正确性 基于KMP算法的数学推导，严格保证循环节判断的正确性。
优势 无需暴力枚举，直接通过数学性质推导结果，高效且代码简洁。
适用场景 需要快速找出数组或字符串的最小循环节的场景，如数据压缩、模式匹配等。

C

问题分析

我们需要找到数组的最小循环子数组，即该数组由其重复拼接而成。核心思路是利用KMP算法中的前缀函数快速推导候选循环节长度，并通过整除验证其有效性。

解题思路

  1. 前缀函数计算：生成前缀数组 pi，pi[i] 表示子数组 nums[0..i] 的最长公共前后缀长度。
  2. 循环节推导：候选循环节长度 d = n - pi[n-1]。
  3. 循环节验证：若 d 能整除 n，则输出前 d 个元素；否则输出原数组。

代码实现

#include <stdio.h>
#include <stdlib.h>

int* ***pute_prefix(int* nums, int n) {
    int* pi = (int*)malloc(n * sizeof(int));
    pi[0] = 0; // 初始前缀长度为0
    
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1]; // 前一个字符的最长公共前后缀长度
        
        // 回溯到更短的公共前后缀
        while (j > 0 && nums[i] != nums[j]) {
            j = pi[j - 1];
        }
        
        // 若当前字符匹配，延长公共前后缀
        if (nums[i] == nums[j]) {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

int main() {
    int n;
    scanf("%d", &n); // 读取数组长度
    
    int* nums = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]); // 读取数组元素
    }
    
    int* pi = ***pute_prefix(nums, n); // 计算前缀数组
    int d = n - pi[n - 1]; // 候选循环节长度
    
    // 验证循环节是否有效
    if (d != 0 && n % d == 0) { 
        // 输出前 d 个元素
        for (int i = 0; i < d; ++i) {
            if (i > 0) printf(" ");
            printf("%d", nums[i]);
        }
    } else { 
        // 输出原数组
        for (int i = 0; i < n; ++i) {
            if (i > 0) printf(" ");
            printf("%d", nums[i]);
        }
    }
    printf("\n");
    
    free(pi);
    free(nums);
    return 0;
}

代码解析

  1. 前缀函数计算

    int* ***pute_prefix(int* nums, int n) {
    int* pi = (int*)malloc(n * sizeof(int));
    pi[0] = 0;
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && nums[i] != nums[j]) {
            j = pi[j - 1]; // 回溯到更短的公共前后缀
        }
        if (nums[i] == nums[j]) {
            j++; // 匹配成功，延长公共前后缀
        }
        pi[i] = j;
    }
    return pi;
}
    • 遍历数组，计算每个位置的最长公共前后缀长度。

  2. 候选循环节长度推导

    int d = n - pi[n - 1];
    • 通过前缀函数最后一个值推导候选循环节长度。

  3. 循环节验证与输出

    if (d != 0 && n % d == 0) {
    // 输出前 d 个元素
} else {
    // 输出原数组
}
    • 若候选长度有效（能整除 n），输出前 d 个元素；否则输出整个数组。

示例测试

  1. 输入示例1
    输入：

    9  
1 2 1 1 2 1 1 2 1

    输出：
    1 2 1
    解析：d=3，数组可分割为3个[1,2,1]。

  2. 输入示例2
    输入：

    6  
1 2 1 2 1 2

    输出：
    1 2
    解析：d=2，数组可分割为3个[1,2]。

  3. 输入示例3
    输入：

    5  
1 2 3 4 5

    输出：
    1 2 3 4 5
    解析：无法找到更小循环节，输出原数组。

综合分析

维度 说明
时间复杂度 O(n)，仅需一次遍历数组计算前缀函数。
空间复杂度 O(n)，存储前缀数组和输入数组。
正确性 基于KMP算法严格推导循环节，覆盖所有边界条件。
优势 高效快速，无需暴力枚举，直接数学推导。
适用场景 大规模数组处理，如数据压缩、周期性模式检测等。

GO

问题分析

我们需要找到数组的最小循环子数组，即该数组可以由某个子数组重复拼接而成。核心思路是利用KMP算法的前缀函数来确定循环节长度，从而高效求解。

解题思路

  1. 前缀函数计算：生成前缀数组 pi，pi[i] 表示子数组 nums[0..i] 的最长公共前后缀长度。
  2. 候选循环节推导：计算候选长度 d = n - pi[n-1]。
  3. 循环验证：若 d 能整除 n，则输出前 d 个元素；否则输出原数组。

代码实现

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

// 计算前缀函数数组
func ***putePrefix(nums []int) []int {
	n := len(nums)
	pi := make([]int, n)
	pi[0] = 0 // 初始位置的前缀长度为0

	for i := 1; i < n; i++ {
		j := pi[i-1] // 前一个字符的最长公共前后缀长度
		// 回溯到更短的公共前后缀
		for j > 0 && nums[i] != nums[j] {
			j = pi[j-1]
		}
		// 若当前字符匹配，延长公共前后缀
		if nums[i] == nums[j] {
			j++
		}
		pi[i] = j
	}
	return pi
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan() // 读取数组长度
	var n int
	fmt.Sscanf(scanner.Text(), "%d", &n)
	
	scanner.Scan() // 读取数组元素
	numsStr := strings.Fields(scanner.Text())
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Sscanf(numsStr[i], "%d", &nums[i])
	}

	pi := ***putePrefix(nums)
	d := n - pi[n-1] // 候选循环节长度

	var result []int
	if d != 0 && n % d == 0 {
		result = nums[:d] // 取前d个元素作为循环节
	} else {
		result = nums // 无法构成循环，输出原数组
	}

	// 格式化输出结果
	fmt.Println(strings.Trim(fmt.Sprint(result), "[]"))
}

代码解析

  1. 输入处理

    scanner.Scan()
fmt.Sscanf(scanner.Text(), "%d", &n)
scanner.Scan()
numsStr := strings.Fields(scanner.Text())
    • 读取数组长度 n 和数组元素字符串，并将其转换为整数数组 nums。

  2. 前缀函数计算

    func ***putePrefix(nums []int) []int {
    pi := make([]int, n)
    for i := 1; i < n; i++ {
        j := pi[i-1]
        for j > 0 && nums[i] != nums[j] {
            j = pi[j-1] // 回溯到更短的公共前后缀
        }
        if nums[i] == nums[j] {
            j++
        }
        pi[i] = j
    }
    return pi
}
    • 遍历数组，计算每个位置的最长公共前后缀长度，填充前缀数组 pi。

  3. 候选循环节推导

    d := n - pi[n-1]
    • 计算候选循环节长度 d = 数组长度 - 前缀数组最后一个元素值。

  4. 循环验证与结果输出

    if d != 0 && n % d == 0 {
    result = nums[:d]
} else {
    result = nums
}
fmt.Println(strings.Trim(fmt.Sprint(result), "[]"))
    • 若候选长度有效，输出前 d 个元素；否则输出原数组。格式化输出元素间用空格分隔。

示例测试

  1. 输入示例1
    输入：

    9  
1 2 1 1 2 1 1 2 1

    输出：
    1 2 1
    解析：前缀数组末尾为6，d=3，数组可重复3次构成原数组。

  2. 输入示例2
    输入：

    6  
1 2 1 2 1 2

    输出：
    1 2
    解析：前缀数组末尾为4，d=2，数组可重复3次构成原数组。

  3. 输入示例3
    输入：

    5  
1 2 3 4 5

    输出：
    1 2 3 4 5
    解析：无法拆分更小循环节，输出原数组。

综合分析

维度 说明
时间复杂度 O(n)，计算前缀函数仅需一次遍历，效率极高。
空间复杂度 O(n)，存储前缀数组和数据数组。
正确性 基于KMP算法的数学推导，严格匹配循环节条件，覆盖所有边界情况。
优势 高效且代码简洁，无需暴力枚举所有可能长度，直接通过数学性质推导最小解。
适用场景 需要快速处理大规模数组的场景，如数据压缩、重复模式检测等。
转载请说明出处内容投诉
CSS教程网 » 华为OD机试真题——最小循环子数组 （2025B卷：100分）Java/python/JavaScript/C/C++/GO最佳实现
谢生

谢生

分享到：

发表评论

欢迎 访客 发表评论

一个令你着迷的主题！

查看演示 官网购买