专栏导读
本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
AI识别到面板上有N（1 ≤ N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠。
由于AI识别误差，每次别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)，
请输出先行后列排序的指示灯的编号，排序规则：
- 每次在尚未排序的灯中挑选最高的灯作为的基准灯，
- 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）。
二、输入描述
第一行为N，表示灯的个数
接下来N行，每行为1个灯的坐标信息，格式为：编号 x1 y1 2 y2
- 编号全局唯一
- 1 ≤ 编号 ≤ 100
- 0 ≤ x1 < x2 ≤ 1000
- 0 ≤ y1 < y2 ≤ 1000
三、输出描述
排序后的编号列表，编号之间以空格分隔。
四、解题思路
- 第一行输入灯的个数N；
- 接下来的N行输入灯的序号和坐标（左上角x1,y1，右下角x2,y2），比如1 1 1 3 3；
- 定义一个等的集合，将灯的序号和坐标以Light对象的形式加入其中；
- 循环灯集合lightList；
- 先行后列，找出未排序最大的灯；
- 找出同一行的灯；
- 按照先行后列进行排序；
- 输出先行后列排序的指示灯的编号。
五、Java算法源码
package com.guor.od;
import java.util.*;
public class OdTest {
static List<Light> lightList = new ArrayList<>();
/**
* 请输出先行后列排序的指示灯的编号
*
* 找出和基准灯属于同一行所有的灯进行排序。
* 两个灯高低偏差不超过灯半径算同一行
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 灯的个数
int N = Integer.parseInt(sc.nextLine());
for (int i = 0; i < N; i++) {
int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int id = nums[0];
int x1 = nums[1];
int y1 = nums[2];
int x2 = nums[3];
int y2 = nums[4];
Light light = new Light(id, x1, y1, x2, y2);
lightList.add(light);
}
while (lightList.size() > 0) {
Light maxLight = getMaxLight();
System.out.print(maxLight.id + " ");
List<Light> sameLineLights = getSameLineLights(maxLight);
sameLineLights.sort(new Comparator<Light>() {
@Override
public int compare(Light l1, Light l2) {
if (l1.x1 < l2.x1)
return -1;
if (l1.x1 > l2.x1)
return 1;
return 0;
}
});
for (Light l : sameLineLights) {
System.out.print(l.id + " ");
}
}
}
// 找出未排序的最大的那个
public static Light getMaxLight() {
Light light = null;
for (Light lt : lightList) {
if (light == null) {
light = lt;
}
if (lt.y1 < light.y1) {
light = lt;
}
if (lt.y1 == light.y1) {
if (lt.x1 < light.x1) {
light = lt;
}
}
}
lightList.remove(light);
return light;
}
public static List<Light> getSameLineLights(Light light) {
List<Light> lights = new ArrayList<>();
for (Light lt : lightList) {
if (lt.y1 == light.y1 || (light.y1 - lt.y1) >= (light.y1 - light.y2) / 2) {
lights.add(lt);
}
}
lightList.removeAll(lights);
return lights;
}
static class Light {
int id, x1, y1, x2, y2;
public Light(int id, int x1, int y1, int x2, int y2) {
super();
this.id = id;
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
}
}
六、效果展示
1、输入
5
1 1 6 3 4
2 4 5 6 3
3 7 4 9 2
4 10 4 12 2
5 5 2 7 0
2、输出
1 2 3 4 5
3、说明
请输出先行后列排序的指示灯的编号。
找出和基准灯属于同一行所有的灯进行排序。
两个灯高低偏差不超过灯半径算同一行。
4、控制台输出
🏆下一篇：华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法
🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。