最新华为OD机试真题-找朋友(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎 在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🎀 找朋友
题目描述
在学校中, 个小朋友站成一队,第
个小朋友的身高为
。每个小朋友都在寻找自己的好朋友,他们的好朋友是指在队伍中站在自己后面第一个比自己高的小朋友。如果第
个小朋友找到了好朋友,那么他的好朋友就是第
个小朋友(要求
)。
现在请你帮忙生成一份列表,列表中的第 个位置表示第
个小朋友的好朋友的位置。如果第
个小朋友找不到好朋友,那么在列表的第
个位置上填
。
输入格式
第一行包含一个正整数 ,表示小朋友的人数。
第二行包含 个正整数,用空格分隔,第
个数表示第
个小朋友的身高
。
输出格式
输出一行,包含 个正整数,用空格分隔,第
个数表示第
个小朋友的好朋友的位置。如果第
个小朋友找不到好朋友,则输出
。
样例输入 1
2
100 95
样例输出 1
0 0
样例输入 2
8
123 124 125 121 119 122 126 123
样例输出 2
1 2 6 5 5 6 0 0
样例1 | 第一个小朋友身高100,站在队尾位置,向队首看,没有比他身高高的小朋友,所以输出第一个值为0。 第二个小朋友站在队首,前面也没有比他身高高的小朋友,所以输出第二个值为0。 |
样例2 | 123的好朋友是1位置上的124 124的好朋友是2位置上的125 125的好朋友是6位置上的126 以此类推 |
数据范围
题解
我们可以从左到右遍历每个小朋友,对于第 个小朋友,我们从
开始向右寻找第一个身高比他高的小朋友,如果找到了,就将该小朋友的位置记录在结果列表的第
个位置上;如果找不到,就在结果列表的第
个位置上记录
。
遍历完所有小朋友后,我们就得到了每个小朋友的好朋友的位置。
时间复杂度为 ,空间复杂度为
。
参考代码
- Python
n = int(input())
heights = list(map(
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测