华为OD机试真题中的“预定酒店”题目是一道典型的算法题,主要考察的是如何在给定的酒店价格数组中找到最接近心理价位的k个酒店,并按价格从低到高输出。以下是对该题目的详细解析:
一、题目描述
放暑假了,小明决定到某旅游景点游玩,他在网上搜索到了各种价位的酒店(长度为n的数组A),他的心理价位是x元,请帮他筛选出k个最接近x元的酒店(n>=k>0),并由低到高打印酒店的价格。
备注:
1)酒店价格数组A和小明的心理价位x均为整型数据;(0 < n,k,x < 10000)
2)优先选择价格最接近心理价位的酒店;若两家酒店和心理价位差价相同,则选择价格较低的酒店。(比如100元和300元距离心理价位200元同样接近,此时选择100元);
3)酒店价格可能相同重复。
二、输入描述
- 第一行:n,k,x,分别表示酒店价格数组的长度、需要筛选出的酒店数量以及小明的心理价位。
- 第二行:A[0] A[1] A[2]…A[n-1],表示酒店的价格数组。
三、输出描述
从低到高打印筛选出的酒店价格。
补充说明:
1)酒店价格数组A和小明的心理价位x均为整型数据
2)优先选择价格最接近心理价位的酒店;若两家酒店距离心理价位差价相同,则选择价格较低的酒店。(比如100元和300元距离心理价位200元同样接近,此时选择100元)
3)酒店价格可能相同重复。
四、示例
示例1:
- 输入:5 3 10 12 15 10 9 11
- 输出:9 10 11
示例2:
- 输入:10 4 6 1 2 3 4 5 6 7 8 9 10
- 输出:4 5 6 7
五、解题思路
-
读取输入:
- 使用
Scanner
类读取输入的n、k、x以及酒店价格数组A。
- 使用
-
计算差值:
- 遍历酒店价格数组A,计算每个酒店价格与心理价位x的差值
diff = |price - x|
。 - 创建一个类(如
HotelPriceDiff
)或数据结构(如Pair
)来存储价格和差值信息,以便后续排序。
- 遍历酒店价格数组A,计算每个酒店价格与心理价位x的差值
-
排序:
- 使用优先队列(最小堆)或自定义排序算法对价格和差值信息进行排序。
- 排序规则:首先按照差值升序排序,如果差值相同则按照价格升序排序。
-
筛选结果:
- 从排序后的结果中取出前k个酒店价格。
- 由于题目要求按价格从低到高输出,可以使用
TreeSet
或PriorityQueue
(最小堆)来自动排序结果,或者手动对结果进行排序。
-
输出:
- 打印筛选出的k个酒店价格。
六、解题策略
-
数据结构选择:
- 使用优先队列(最小堆)可以高效地获取最接近心理价位的k个酒店,因为优先队列可以在O(log k)时间内完成插入和删除操作。
- 使用
TreeSet
可以自动对结果进行排序,但需要注意TreeSet
的插入和删除操作时间复杂度为O(log n)。
-
算法效率:
- 遍历酒店价格数组计算差值的时间复杂度为O(n)。
- 优先队列的插入和删除操作时间复杂度为O(log k),因此整体排序的时间复杂度为O(n log k)。
- 如果使用
TreeSet
进行排序,则整体排序的时间复杂度为O(n log n),但在k较小且n较大时,优先队列通常更高效。
-
内存使用:
- 优先队列和
TreeSet
都会占用额外的内存来存储元素和进行比较操作。 - 如果内存使用是一个关键因素,可以考虑使用数组和手动排序算法来减少内存占用。
- 优先队列和
七、代码实现(队列)
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;
public class HotelSelection {
// 定义一个内部类来存储价格和差值信息
static class HotelPriceDiff {
int price;
int diff;
HotelPriceDiff(int price, int diff) {
this.price = price;
this.diff = diff;
}
}
public static void main(String[] args) {
// 创建Scanner对象以读取输入
Scanner scanner = new Scanner(System.in);
// 读取输入
int n = scanner.nextInt(); // 酒店数量
int k = scanner.nextInt(); // 需要选择的酒店数量
int x = scanner.nextInt(); // 顾客的心理价位
// 创建一个数组来存储每家酒店的价格
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
prices[i] = scanner.nextInt();
}
// 使用优先队列(最小堆)来存储价格和差值信息
PriorityQueue<HotelPriceDiff> pq = new PriorityQueue<>(
(a, b) -> {
// 自定义比较规则:首先按照差值升序排序,差值相同则按照价格升序排序
if (a.diff != b.diff) {
return Integer.compare(a.diff, b.diff);
} else {
return Integer.compare(a.price, b.price);
}
}
);
// 计算每个酒店价格与顾客心理价位的差值,并将酒店信息加入优先队列
for (int price : prices) {
int diff = Math.abs(price - x);
pq.offer(new HotelPriceDiff(price, diff));
}
// 从优先队列中取出前k个最接近心理价位的酒店价格
TreeSet<Integer> result = new TreeSet<>(); // 使用TreeSet自动排序结果
while (!pq.isEmpty() && result.size() < k) {
result.add(pq.poll().price);
}
// 打印结果
for (int price : result) {
System.out.print(price + " ");
}
}
}
八、代码实现(数组)
import java.util.*;
public class HotelReservation {
// 定义一个内部类来存储价格和差值
static class PriceDiff {
int diff;
int price;
PriceDiff(int diff, int price) {
this.diff = diff;
this.price = price;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入
int n = scanner.nextInt();
int k = scanner.nextInt();
int x = scanner.nextInt();
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
prices[i] = scanner.nextInt();
}
// 计算差值并存储在一个列表中
List<PriceDiff> priceDiffs = new ArrayList<>();
for (int price : prices) {
int diff = Math.abs(price - x);
priceDiffs.add(new PriceDiff(diff, price));
}
// 根据差值排序,如果差值相同则按价格排序
Collections.sort(priceDiffs, Comparator.comparingInt(a -> a.diff).thenComparingInt(a -> a.price));
// 筛选前k个价格
List<Integer> topKPrices = new ArrayList<>();
for (int i = 0; i < k; i++) {
topKPrices.add(priceDiffs.get(i).price);
}
// 对结果排序(虽然已经在上一步中按差值排序过,但题目要求按价格排序,这里再次确保)
Collections.sort(topKPrices);
// 输出结果
for (int price : topKPrices) {
System.out.print(price + " ");
}
}
}
示例1:
输入:5 3 10 12 15 10 9 11
输出:9 10 11
九、注意事项
- 输入验证:在实际应用中,需要对输入进行验证,确保n、k、x以及价格数组A的输入格式正确。
- 性能优化:在处理大规模数据时,需要注意算法的性能优化,如使用更高效的数据结构或算法来减少时间复杂度。
- 边界情况:需要考虑边界情况,如k等于n、价格数组A中有重复价格等。
十、运行实例解析
输入
10 5 6
1 2 3 4 5 6 7 8 9 10
-
读取输入:
-
n = 10
:表示酒店价格数组的长度。 -
k = 5
:表示需要筛选出的最接近心理价位的酒店数量。 -
x = 6
:表示小明的心理价位。 -
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
:表示酒店的价格数组。
-
-
计算差值:
- 对于每个价格,计算其与心理价位
x
的差值diff = |price - x|
。
- 对于每个价格,计算其与心理价位
-
使用优先队列(最小堆):
- 创建一个优先队列,按照差值升序排序,差值相同时按价格升序排序。
- 将每个价格及其差值加入优先队列。
-
筛选前k个价格:
- 从优先队列中依次取出前
k
个元素(即最接近心理价位的酒店价格)。 - 由于优先队列已经按照差值和价格排序,所以取出的前
k
个元素就是符合条件的酒店价格。
- 从优先队列中依次取出前
-
输出结果:
- 将筛选出的酒店价格按升序打印出来。
十一、运行步骤
-
初始化优先队列。
-
遍历价格数组
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
,计算差值并加入优先队列:-
1
:差值5
-
2
:差值4
-
3
:差值3
-
4
:差值2
-
5
:差值1
-
6
:差值0
(最接近) -
7
:差值1
-
8
:差值2
-
9
:差值3
-
10
:差值4
优先队列中的元素(按差值和价格排序)将是:
(6, 0)
(5, 1)
(7, 1)
(4, 2)
(8, 2)
(3, 3)
(9, 3)
(2, 4)
(10, 4)
-
(1, 5)
(但实际上我们只需要前5个)
-
-
从优先队列中取出前5个元素:
6
5
7
4
8
-
打印输出结果:
4 5 6 7 8
十二、结论
对于给定的输入,程序将正确地筛选出最接近心理价位6
的5个酒店价格,并按升序打印出来。输出结果为4 5 6 7 8
,与预期相符。