【最新华为OD机试E卷】高矮个子排队(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🌲 高矮个子排队

问题描述

有一队小朋友站成一排，他们的身高各不相同。我们用一个正整数数组来表示这队小朋友的身高，例如 {}。

现在我们希望将这些小朋友重新排队，使他们按照"高""矮""高""矮"的顺序排列。具体要求如下：

1. 每个"高"位置的小朋友要比相邻位置的小朋友高或者一样高。
2. 每个"矮"位置的小朋友要比相邻位置的小朋友矮或者一样矮。
3. 小朋友们移动的总距离要最小。
4. 排队从"高"位置开始。

例如，对于小队 {}，一个满足条件的排序结果是 {}。

注意，虽然 {} 也满足"高""矮""高""矮"的顺序，但小朋友们的移动距离较大，所以不是最优结果。

移动距离的定义如下：

• 如果一个小朋友从第二位移到第三位，移动距离为 。
• 如果移动到第四位，移动距离为 ，以此类推。

输入格式

输入为一行，包含若干个用空格分隔的正整数，表示小朋友们的身高。

输出格式

输出为一行，包含若干个用空格分隔的正整数，表示重新排序后小朋友们的身高。

样例输入1

4 1 3 5 2

样例输出1

4 1 5 2 3

样例输入2

1 1 1 1 1

样例输出2

1 1 1 1 1

样例输入3

xxx

样例输出3

[]

样例解释

数据范围

• 小朋友数量 满足
• 身高 满足

题解

模拟排序

这道题目要求我们将一队小朋友按照"高""矮""高""矮"的顺序重新排列，同时要求移动距离最小。解题的关键在于理解题目要求和找到一个高效的排序方法。

首先，我们需要明白"高""矮"交替的含义：

1. 奇数位置（第1、3、5...位）的小朋友应该比相邻的小朋友高或相等。
2. 偶数位置（第2、4、6...位）的小朋友应该比相邻的小朋友矮或相等。

解决这个问题的一个有效方法是使用冒泡排序的思想，但我们只需要进行一次遍历：

1. 从左到右遍历数组。
2. 对于奇数位置，如果当前小朋友比右边的矮，就交换它们。
3. 对于偶数位置，如果当前小朋友比右边的高，就交换它们。

这个方法之所以有效，是因为：

1. 它保证了奇数位置的小朋友总是不低于偶数位置的小朋友。
2. 每次交换都是相邻位置的交换，保证了移动距离最小。
3. 一次遍历就能完成排序，因为我们只需要保证相邻位置的大小关系正确。

时间复杂度分析：

• 算法只需要遍历一次数组，所以时间复杂度是 ，其中 是小朋友的数量。
• 对于给定的数据范围（），这个复杂度是完全可以接受的。

需要注意的是，我们还需要处理输入可能非法的情况，比如输入不是数字时，应该返回空数组。

这个解法的优点是简单直观，容易实现，而且能够保证最小的移动距离。

参考代码

• Python

def rearrange_heights(heights):
    # 检查输入是否合法
    if not all(isinstance(h, int) and h > 0 for h in heights):
        return []
    
    n = len(heights)
    # 如果只有一个小朋友，直接返回
    if n == 1:
        return heights
    
    # 遍历数组，调整相邻小朋友的位置
    for i in range(n - 1):
        if i % 2 == 0:  # 奇数位置（索引从0开始）
            if heights[i] < heights[i + 1]:
                heights[i], heights[i + 1] = heights[i + 1], heights[i]
        else:  # 偶数位置
            if heights[i] > heights[i + 1]:
                heights[i], heights[i + 1] = heights[i + 1], heights[i]
    
    return heights

# 读取输入
try:
    heights = list(map(int, input().split()))
    result = rearrange_heights(heights)
    print(' '.join(map(str, result)))
except ValueError:
    print('[]')

• C

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

#define MAX_N 100

// 交换两个整数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 重新排列小朋友的身高
void rearrange_heights(int *heights, int n) {
    for (int i = 0; i < n - 1; i++) {
        if (i % 2 == 0) {  // 奇数位置
            if (heights[i] < heights[i + 1]) {
                swap(&heights[i], &heights[i + 1]);
            }
        } else {  // 偶数位置
            if (heights[i] > heights[i + 1]) {
                swap(&heights[i], &heights[i + 1]);
            }
        }
    }
}

int main() {
    char input[1000];
    int heights[MAX_N];
    int n = 0;

    // 读取输入
    if (fgets(in