解题思路

题目要求把队伍里最高的和最矮的两个同学交换位置，其他人不动。

思路分三步：

1. 找位置：遍历数组，记录最高的人在哪、最矮的人在哪
2. 交换：把这两个位置的值互换
3. 输出：按顺序输出整个数组

怎么同时找最高和最矮？

用两个变量 hi 和 lo 分别记住最高和最矮的位置，一开始都设为第 1 个。

然后从第 2 个开始遍历：

• 遇到比 a[hi] 高的，更新 hi
• 遇到比 a[lo] 矮的，更新 lo

遍历完，hi 就是最高的位置，lo 就是最矮的位置，把这两个位置的值交换就行。

参考代码

#include <iostream>
using namespace std;

int main() {
    int n, a[100];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    // 找最高和最矮的位置
    int hi = 0, lo = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[hi]) hi = i;
        if (a[i] < a[lo]) lo = i;
    }

    // 交换
    int t = a[hi];
    a[hi] = a[lo];
    a[lo] = t;

    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，只遍历一遍数组
• 空间复杂度：O(N)，一个数组存身高