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

华为OD机试 - 优雅子数组 - 暴力枚举（Python/JS/C/C++ 2024 E卷 100分）

news 2025/3/22 6:03:11

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

如果一个数组中出现次数最多的元素出现大于等于 K 次，称为 k 优雅数组，k 可以被称为优雅阈值。

例如，数组 [2, 3, 1, 2, 3, 1, 2, 3, 1]，它是一个 3 优雅数组，因为元素 1 出现次数大于等于 3 次，数组 [2, 3, 1, 2, 3, 1] 不是一个 3 优雅数组，因为其中出现次数最多的元素是 1 和 2，只出现了 2 次。

给定一个数组 A 和 k 值，请求出 A 有多少子数组是 k-优雅子数组。

子数组是数组中一个或多个连续元素组成的数组。

例如，数组 [1, 2, 3, 4] 包含 10 个子数组，分别是：

[1]，[1, 2]，[1, 2, 3]，[1, 2, 3, 4]，[2]，[2, 3]，[2, 3, 4]，[3]，[3, 4]，[4]。

二、输入描述

第一行输入两个整数，用空格隔开，含义是：A 数组长度和 k 值

第二行输入 A 数组元素，以空格隔开

三、输出描述

输出 A 有多少子数组是 k-优雅子数组

四、测试用例

测试用例1：

1、输入

7 3
1 2 3 1 2 3 1

2、输出

3、说明

只有整个数组 [1,2,3,1,2,3,1] 中元素 1 出现了3次。

测试用例2：

1、输入

7 2
1 2 3 1 2 3 1

2、输出

3、说明

共有10个子数组中至少有一个元素出现了2次或更多。

五、解题思路

读取数组长度n和优雅阈值k
初始化结果计数器，用于统计k-优雅子数组的数量
遍历所有可能的子数组起始点
使用HashMap记录当前子数组中每个元素的出现次数
遍历所有可能的子数组终止点
- 更新当前元素的出现次数
- 更新最大出现次数
- 如果最大出现次数达到或超过k，计数器加一
输出结果

六、Python算法源码

# 导入所需的库
from collections import defaultdict
import sysdef main():# 读取所有输入input = sys.stdin.read().split()idx = 0# 读取数组长度n和优雅阈值kn = int(input[idx])k = int(input[idx + 1])idx += 2# 读取数组A的元素A = list(map(int, input[idx:idx + n]))idx += n# 初始化结果计数器，用于统计k-优雅子数组的数量result = 0# 遍历所有可能的子数组起始点for start in range(n):# 使用字典记录当前子数组中每个元素的出现次数freq_map = defaultdict(int)# 记录当前子数组中元素的最大出现次数max_freq = 0# 遍历所有可能的子数组终止点for end in range(start, n):current = A[end]# 更新当前元素的出现次数freq_map[current] += 1# 更新最大出现次数if freq_map[current] > max_freq:max_freq = freq_map[current]# 如果最大出现次数达到或超过k，计数器加一if max_freq >= k:result += 1# 输出结果print(result)if __name__ == "__main__":main()

七、JavaScript算法源码

// 使用 Node.js 的 readline 模块读取输入
const readline = require('readline');// 创建接口
const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});let input = [];
let n = 0;
let k = 0;
let A = [];// 监听每一行输入
rl.on('line', function(line){input.push(line);
}).on('close', function(){// 读取数组长度n和优雅阈值klet firstLine = input[0].trim().split(' ');n = parseInt(firstLine[0]);k = parseInt(firstLine[1]);// 读取数组A的元素A = input[1].trim().split(' ').map(Number);// 初始化结果计数器let result = 0;// 遍历所有可能的子数组起始点for(let start = 0; start < n; start++) {// 使用对象记录当前子数组中每个元素的出现次数let freqMap = {};// 记录当前子数组中元素的最大出现次数let maxFreq = 0;// 遍历所有可能的子数组终止点for(let end = start; end < n; end++) {let current = A[end];// 更新当前元素的出现次数if(freqMap[current] === undefined){freqMap[current] = 1;}else{freqMap[current] += 1;}// 更新最大出现次数if(freqMap[current] > maxFreq){maxFreq = freqMap[current];}// 如果最大出现次数达到或超过k，计数器加一if(maxFreq >= k){result += 1;}}}// 输出结果console.log(result);
});

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义队列节点结构体
typedef struct Node {int num; // 客户编号struct Node* next; // 指向下一个节点
} Node;// 定义队列结构体
typedef struct Queue {Node* front; // 队首Node* rear;  // 队尾
} Queue;// 初始化队列
void initQueue(Queue* q){q->front = q->rear = NULL;
}// 判断队列是否为空
int isEmpty(Queue* q){return q->front == NULL;
}// 入队操作
void enqueue(Queue* q, int num){Node* newNode = (Node*)malloc(sizeof(Node));newNode->num = num;newNode->next = NULL;if(isEmpty(q)){q->front = q->rear = newNode;}else{q->rear->next = newNode;q->rear = newNode;}
}// 出队操作，返回客户编号
int dequeue(Queue* q){if(isEmpty(q)){return -1; // 表示队列为空}Node* temp = q->front;int num = temp->num;q->front = q->front->next;if(q->front == NULL){q->rear = NULL;}free(temp);return num;
}int main(){int n, k;// 读取数组长度n和优雅阈值kscanf("%d %d", &n, &k);// 读取数组A的元素int* A = (int*)malloc(n * sizeof(int));for(int i = 0; i < n; i++){scanf("%d", &A[i]);}// 初始化结果计数器int result = 0;// 遍历所有可能的子数组起始点for(int start = 0; start < n; start++){// 使用动态数组记录元素频率int freq[100001] = {0}; // 假设元素范围为1到100000int maxFreq = 0;// 遍历所有可能的子数组终止点for(int end = start; end < n; end++){int current = A[end];freq[current]++;if(freq[current] > maxFreq){maxFreq = freq[current];}// 如果最大出现次数达到或超过k，计数器加一if(maxFreq >= k){result++;}}}// 输出结果printf("%d\n", result);// 释放内存free(A);return 0;
}

九、C++算法源码

int main(){ios::sync_with_stdio(false);cin.tie(NULL);int n, k;// 读取数组长度n和优雅阈值kcin >> n >> k;// 读取数组A的元素vector<int> A(n);for(int i = 0; i < n; i++) {cin >> A[i];}// 初始化结果计数器int result = 0;// 遍历所有可能的子数组起始点for(int start = 0; start < n; start++){// 使用unordered_map记录当前子数组中每个元素的出现次数unordered_map<int, int> freqMap;// 记录当前子数组中元素的最大出现次数int maxFreq = 0;// 遍历所有可能的子数组终止点for(int end = start; end < n; end++){int current = A[end];// 更新当前元素的出现次数freqMap[current]++;// 更新最大出现次数if(freqMap[current] > maxFreq){maxFreq = freqMap[current];}// 如果最大出现次数达到或超过k，计数器加一if(maxFreq >= k){result++;}}}// 输出结果cout << result << "\n";return 0;
}