一、题目描述
现在有一队小朋友，他们高矮不同，我们以正整数数组表示这一队小朋友的身高，如数组{5,3,1,2,3}。
我们现在希望小朋友排队，以“高”“矮”“高”“矮”顺序排列，每一个“高”位置的小朋友要比相邻的位置高或者相等；每一个“矮”位置的小朋友要比相邻的位置矮或者相等；
要求小朋友们移动的距离和最小，第一个从“高”位开始排，输出最小移动距离即可。
例如，在示范小队{5,3,1,2,3}中，{5, 1, 3, 2, 3}是排序结果。{5, 2, 3, 1, 3} 虽然也满足“高”“矮”“高”“矮”顺序排列，但小朋友们的移动距离大，所以不是最优结果。
移动距离的定义如下所示：
第二位小朋友移到第三位小朋友后面，移动距离为1，若移动到第四位小朋友后面，移动距离为2；
二、输入描述
排序前的小朋友，以英文空格的正整数：
4 3 5 7 8
注：小朋友<100个
三、输出描述
排序后的小朋友，以英文空格分割的正整数：
4 3 7 5 8
四、解题思路
题目要求将小朋友按照“高”“矮”“高”“矮”的顺序排列，并使得小朋友们的移动距离最小。
我们可以使用交换元素的方式来实现排序，同时记录交换的次数，即移动距离。
具体步骤如下：
- 读取输入的字符串，使用空格分割得到一个字符串数组；
- 将字符串数组转换为整型数组arr；
- 初始化变量i为0，表示当前位置；
- 使用while循环，判断是否可以进行交换，即判断i+1是否小于数组长度；
- 在循环内部，根据当前位置的奇偶性进行交换判断。
- 如果i是奇数，则当前位置为“矮”位，即小朋友的身高应小于或等于下一个位置的小朋友身高。如果不满足条件，交换两个位置的小朋友，并增加移动距离。
- 如果i是偶数，则当前位置为“高”位，即小朋友的身高应大于或等于下一个位置的小朋友身高。如果不满足条件，交换两个位置的小朋友，并增加移动距离。
- 每次循环结束后，将i增加1，继续下一轮的判断；
- 循环结束后，输出排列后的整型数组arr，每个数字之间用空格分割。
该算法采用了一种贪心的思路，通过遍历数组，根据当前位置的奇偶性进行交换判断，以满足“高”“矮”“高”“矮”的顺序排列。
算法在每次交换时记录了移动距离，即交换的次数，最终输出移动距离最小的排序结果。
算法的时间复杂度为O(n)，其中n为小朋友的个数。在每次循环中，只进行了常数次的比较和交换操作。
五、Java算法源码
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 将输入字符串按空格分割成字符串数组，并将字符串数组转换为整数数组
int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 当前位置
int i = 0;
while (i +1 < arr.length){
// 偶数位置，即“高”位
if ((i+1) % 2 == 0){
// 当前位置大于下一个位置，需要进行交换
if (arr[i] > arr[i+1]){
int tem = arr[i+1];
arr[i +1] = arr[i];
arr[i] = tem;
}
}else {// 奇数位置，即“矮”位
// 当前位置小于下一个位置，需要进行交换
if (arr[i] < arr[i+1]){
int tem = arr[i+1];
arr[i +1] = arr[i];
arr[i] = tem;
}
}
i++;
}
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j]+" ");
}
}
六、效果展示
🏆下一篇：华为OD机试真题 Java 实现【跳房子II】【2023 B卷 100分】，附详细解题思路
🏆本文收录于，华为OD机试（JAVA）（2022&2023）
本专栏包含了最新最全的2023年华为OD机试真题，有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新，每天在线答疑。