找朋友 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 100分

题解： Java / Python / C++

题目描述

在学校中，N个小朋友站成一队，第i个小朋友的身高为height[i] 第i个小朋友可以看到的第一个比自己身高更高的小朋友j，那么是i的好朋友(要求j>i)。

请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。 小朋友人数范围是[0,40000]。

输入描述

第一行输入N，N表示有N个小朋友

第二行输入N个小朋友的身高height[i]，都是整数

输出描述

输出N个小朋友的好朋友的位置

示例1

输入：
2
100 95

输出：
0 0

说明：
第一个小朋友身高100，站在队尾位置，向队首看，没有比他身高高的小朋友，所以输出第一个值为0。
第二个小朋友站在队首，前面也没有比他身高高的小朋友，所以输出第二个值为0。

示例2

输入：
8
123 124 125 121 119 122 126 123

输出：
1 2 6 5 5 6 0 0

说明：
123的好朋友是1位置上的124
124的好朋友是2位置上的125
125的好朋友是6位置上的126
以此类推

题解

暴力解法：使用双重循环，外循环遍历每个小朋友，内循环寻找当前小朋友右侧第一个比自己高的小朋友。

这种方法的时间复杂度是 O(N^2)，在最坏情况下效率不高，不适合大数据量。

当数据量较大时可以使用栈优化：利用栈数据结构，可以将时间复杂度降低到 O(N)。

Java

import java.util.Scanner;
import java.util.Arrays;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入的整数 n
        int n = scanner.nextInt();

        // 初始化高度数组
        int[] height = new int[n];
        for (int i = 0; i < n; i++) {
            height[i] = scanner.nextInt();
        }

        // 结果数组
        int[] ans = new int[n];

        // 找到每个高度之后第一个更高的人的位置
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (height[i] < height[j]) {
                    ans[i] = j;
                    break;
                }
            }
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            if (i + 1 == n) {
                System.out.println(ans[i]);
            } else {
                System.out.print(ans[i] + " ");
            }
        }
    }
}

Python

n = int(input())

s = input().strip()

# 提供的测试用例有问题，以下2行不写只能 AC 95%
if s[-1] == '}':
    s = s[:-1]

height = list(map(int, s.split()))

rs = [0] * n

for  i in range(n):
    for j in range(i+1, n):
        if height[j] > height[i]:
            rs[i] = j
            break

print(*rs)    
// AC

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> height(n);
    for (int i = 0; i < n; i++) cin >> height[i];

    vector<int> ans(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (height[i] < height[j]) {
                ans[i] = j;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (i + 1 == n) {
            cout << ans[i] << endl;
        } else {
            cout << ans[i] << " ";
        }
    }

    return 0;
}    

希望这个专栏不仅能帮您成功通过华为机试，还能让您熟练掌握算法。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏