当前位置：首页 > news >正文

华为OD机试 - 几何平均值最大子数（Python/JS/C/C++ 2024 E卷 200分）

news 2025/5/2 6:46:12

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

从一个长度为N的正整数数组numbers中找出长度至少为L且几何平均值Q最大的子数组，并输出其位置和大小。（K个数的几何平均值为K个数的乘积的K次方根）

若有多个子数组的几何平均值均为最大值Q，则输出长度最小的子数组。

若有多个长度最小的子数组的几何平均值均为最大值，则输出最前面的子数组。

二、输入描述

第1行输入N、L：

N表示numbers的大小（1 <= N <= 100000）

L表示子数组的最小长度（1 <= L <= N）

之后N行表示numbers中的N个数，每行一个（1 <= numbers[i] <= 10^9）

三、输出描述

输出子数组的位置（从0开始计数）和大小，中间用一个空格隔开。

备注
用例保证除几何平均值为最大值的子数组外，其他子数组的几何平均值至少比最大值小10^-10倍。

四、测试用例

测试用例1：

1、输入

3 2
2
2
3

2、输出

1 2

3、说明

长度至少为2的子数组共有三个，分别是{2,2}, {2,3}, {2,3}，其中{2,3}的几何平均值最大，故输出其位置1和长度2。

测试用例2：

1、输入

10 2
0.2
0.2
0.1
0.2
0.2
0.2
0.1
0.2
0.2
0.2

2、输出

0 2

3、说明

所有长度为2的子数组及其几何平均值：

索引0-1: [0.2, 0.2]，GM = 0.2
索引1-2: [0.2, 0.1]，GM ≈ 0.141
索引2-3: [0.1, 0.2]，GM ≈ 0.141
索引3-4: [0.2, 0.2]，GM = 0.2
索引4-5: [0.2, 0.2]，GM = 0.2
索引5-6: [0.2, 0.1]，GM ≈ 0.141
索引6-7: [0.1, 0.2]，GM ≈ 0.141
索引7-8: [0.2, 0.2]，GM = 0.2
索引8-9: [0.2, 0.2]，GM = 0.2

最大几何平均值为0.2，对应多个子数组。选择最早的子数组，即从索引0开始的子数组，因此输出0 2。

五、解题思路

1、问题分析

我们需要在一个长度为N的正数数组numbers中找出长度至少为L且几何平均值最大的子数组，并输出其起始位置和长度。如果存在多个满足条件的子数组，我们需要按照以下优先级选择：

几何平均值最大的子数组。
如果有多个几何平均值相同，选择长度最小的子数组。
如果仍有多个，选择最前面的子数组。

由于N的范围较大（1 ≤ N ≤ 100,000），需要设计一个高效的算法。

2、具体步骤：

读取输入：读取N和L，接着读取N个正数。
对数转换：对每个数取自然对数，存储在一个数组中。
前缀和计算：计算对数数组的前缀和，以便快速计算任意子数组的对数和。
滑动窗口遍历：遍历所有长度为L的子数组，计算其对数和，记录最大对数和及其起始位置。
输出结果：输出起始位置和子数组长度L。

六、Python算法源码

import math
import sysdef main():# 读取输入input = sys.stdin.read().split()index = 0# 读取数组大小N和子数组最小长度LN = int(input[index])index += 1L = int(input[index])index += 1# 初始化数组并计算对数值log_values = []for _ in range(N):num = float(input[index])index += 1log_values.append(math.log(num))  # 计算每个数的自然对数# 计算前缀和数组prefix_sums = [0.0] * (N + 1)for i in range(1, N + 1):prefix_sums[i] = prefix_sums[i - 1] + log_values[i - 1]# 初始化最大对数平均值及对应子数组的起始位置和长度max_log_average = -math.infresult_start_index = 0result_length = L# 初始化最小前缀和及其索引min_prefix = 0.0min_prefix_index = 0# 遍历前缀和数组，寻找最大对数平均值的子数组for i in range(L, N + 1):# 更新最小前缀和为[0, i - L]区间的最小前缀和if prefix_sums[i - L] < min_prefix:min_prefix = prefix_sums[i - L]min_prefix_index = i - L# 计算当前对数平均值current_log_average = (prefix_sums[i] - min_prefix) / L# 更新最大对数平均值及对应的子数组位置和长度if current_log_average > max_log_average:max_log_average = current_log_averageresult_start_index = min_prefix_indexresult_length = Lelif math.isclose(current_log_average, max_log_average, abs_tol=1e-10):# 如果对数平均值相同，选择长度更小的子数组if L < result_length:result_start_index = min_prefix_indexresult_length = L# 如果长度相同，选择起始位置更靠前的子数组（无需操作，因为遍历顺序已保证）# 输出结果print(result_start_index, result_length)if __name__ == "__main__":main()

七、JavaScript算法源码

// 引入readline模块以读取输入
const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = [];
rl.on('line', function(line){input = input.concat(line.trim().split(' '));
}).on('close', function(){let index = 0;// 读取数组大小N和子数组最小长度Lconst N = parseInt(input[index++]);const L = parseInt(input[index++]);// 初始化数组并计算对数值const logValues = [];for(let i = 0; i < N; i++){const num = parseFloat(input[index++]);logValues.push(Math.log(num)); // 计算每个数的自然对数}// 计算前缀和数组const prefixSums = new Array(N + 1).fill(0);for(let i = 1; i <= N; i++){prefixSums[i] = prefixSums[i - 1] + logValues[i - 1];}// 初始化最大对数平均值及对应子数组的起始位置和长度let maxLogAverage = -Infinity;let resultStartIndex = 0;let resultLength = L;// 初始化最小前缀和及其索引let minPrefix = 0.0;let minPrefixIndex = 0;// 遍历前缀和数组，寻找最大对数平均值的子数组for(let i = L; i <= N; i++){// 更新最小前缀和为[0, i - L]区间的最小前缀和if(prefixSums[i - L] < minPrefix){minPrefix = prefixSums[i - L];minPrefixIndex = i - L;}// 计算当前对数平均值const currentLogAverage = (prefixSums[i] - minPrefix) / L;// 更新最大对数平均值及对应的子数组位置和长度if(currentLogAverage > maxLogAverage){maxLogAverage = currentLogAverage;resultStartIndex = minPrefixIndex;resultLength = L;} else if(Math.abs(currentLogAverage - maxLogAverage) < 1e-10){// 如果对数平均值相同，选择长度更小的子数组if(L < resultLength){resultStartIndex = minPrefixIndex;resultLength = L;}// 如果长度相同，选择起始位置更靠前的子数组（无需操作，因为遍历顺序已保证）}}// 输出结果console.log(resultStartIndex + " " + resultLength);
});

八、C算法源码

#include <stdio.h>
#include <math.h>
#include <float.h>int main(){int N, L;// 读取数组大小N和子数组最小长度Lscanf("%d %d", &N, &L);double log_values[N];// 读取数组元素并计算对数值for(int i = 0; i < N; i++){double num;scanf("%lf", &num);log_values[i] = log(num); // 计算每个数的自然对数}// 计算前缀和数组double prefix_sums[N + 1];prefix_sums[0] = 0.0;for(int i = 1; i <= N; i++){prefix_sums[i] = prefix_sums[i - 1] + log_values[i - 1];}// 初始化最大对数平均值及对应子数组的起始位置和长度double max_log_average = -DBL_MAX;int result_start_index = 0;int result_length = L;// 初始化最小前缀和及其索引double min_prefix = 0.0;int min_prefix_index = 0;// 遍历前缀和数组，寻找最大对数平均值的子数组for(int i = L; i <= N; i++){// 更新最小前缀和为[0, i - L]区间的最小前缀和if(prefix_sums[i - L] < min_prefix){min_prefix = prefix_sums[i - L];min_prefix_index = i - L;}// 计算当前对数平均值double current_log_average = (prefix_sums[i] - min_prefix) / L;// 更新最大对数平均值及对应的子数组位置和长度if(current_log_average > max_log_average){max_log_average = current_log_average;result_start_index = min_prefix_index;result_length = L;}else if(fabs(current_log_average - max_log_average) < 1e-10){// 如果对数平均值相同，选择长度更小的子数组if(L < result_length){result_start_index = min_prefix_index;result_length = L;}// 如果长度相同，选择起始位置更靠前的子数组（无需操作，因为遍历顺序已保证）}}// 输出结果printf("%d %d\n", result_start_index, result_length);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int N, L;// 读取数组大小N和子数组最小长度Lcin >> N >> L;vector<double> log_values(N);// 读取数组元素并计算对数值for(int i = 0; i < N; i++){double num;cin >> num;log_values[i] = log(num); // 计算每个数的自然对数}// 计算前缀和数组vector<double> prefix_sums(N + 1, 0.0);for(int i = 1; i <= N; i++){prefix_sums[i] = prefix_sums[i - 1] + log_values[i - 1];}// 初始化最大对数平均值及对应子数组的起始位置和长度double max_log_average = -1e308; // 接近负无穷int result_start_index = 0;int result_length = L;// 初始化最小前缀和及其索引double min_prefix = 0.0;int min_prefix_index = 0;// 遍历前缀和数组，寻找最大对数平均值的子数组for(int i = L; i <= N; i++){// 更新最小前缀和为[0, i - L]区间的最小前缀和if(prefix_sums[i - L] < min_prefix){min_prefix = prefix_sums[i - L];min_prefix_index = i - L;}// 计算当前对数平均值double current_log_average = (prefix_sums[i] - min_prefix) / L;// 更新最大对数平均值及对应子数组的位置和长度if(current_log_average > max_log_average){max_log_average = current_log_average;result_start_index = min_prefix_index;result_length = L;}else if(abs(current_log_average - max_log_average) < 1e-10){// 如果对数平均值相同，选择长度更小的子数组if(L < result_length){result_start_index = min_prefix_index;result_length = L;}// 如果长度相同，选择起始位置更靠前的子数组（无需操作，因为遍历顺序已保证）}}// 输出结果cout << result_start_index << " " << result_length << "\n";return 0;
}