华为OD机试真题---预定酒店


华为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

五、解题思路

  1. 读取输入

    • 使用Scanner类读取输入的n、k、x以及酒店价格数组A。
  2. 计算差值

    • 遍历酒店价格数组A,计算每个酒店价格与心理价位x的差值diff = |price - x|
    • 创建一个类(如HotelPriceDiff)或数据结构(如Pair)来存储价格和差值信息,以便后续排序。
  3. 排序

    • 使用优先队列(最小堆)或自定义排序算法对价格和差值信息进行排序。
    • 排序规则:首先按照差值升序排序,如果差值相同则按照价格升序排序。
  4. 筛选结果

    • 从排序后的结果中取出前k个酒店价格。
    • 由于题目要求按价格从低到高输出,可以使用TreeSetPriorityQueue(最小堆)来自动排序结果,或者手动对结果进行排序。
  5. 输出

    • 打印筛选出的k个酒店价格。

六、解题策略

  1. 数据结构选择

    • 使用优先队列(最小堆)可以高效地获取最接近心理价位的k个酒店,因为优先队列可以在O(log k)时间内完成插入和删除操作。
    • 使用TreeSet可以自动对结果进行排序,但需要注意TreeSet的插入和删除操作时间复杂度为O(log n)。
  2. 算法效率

    • 遍历酒店价格数组计算差值的时间复杂度为O(n)。
    • 优先队列的插入和删除操作时间复杂度为O(log k),因此整体排序的时间复杂度为O(n log k)。
    • 如果使用TreeSet进行排序,则整体排序的时间复杂度为O(n log n),但在k较小且n较大时,优先队列通常更高效。
  3. 内存使用

    • 优先队列和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

九、注意事项

  1. 输入验证:在实际应用中,需要对输入进行验证,确保n、k、x以及价格数组A的输入格式正确。
  2. 性能优化:在处理大规模数据时,需要注意算法的性能优化,如使用更高效的数据结构或算法来减少时间复杂度。
  3. 边界情况:需要考虑边界情况,如k等于n、价格数组A中有重复价格等。

十、运行实例解析

输入
10 5 6
1 2 3 4 5 6 7 8 9 10
  1. 读取输入

    • n = 10:表示酒店价格数组的长度。
    • k = 5:表示需要筛选出的最接近心理价位的酒店数量。
    • x = 6:表示小明的心理价位。
    • A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]:表示酒店的价格数组。
  2. 计算差值

    • 对于每个价格,计算其与心理价位x的差值diff = |price - x|
  3. 使用优先队列(最小堆)

    • 创建一个优先队列,按照差值升序排序,差值相同时按价格升序排序。
    • 将每个价格及其差值加入优先队列。
  4. 筛选前k个价格

    • 从优先队列中依次取出前k个元素(即最接近心理价位的酒店价格)。
    • 由于优先队列已经按照差值和价格排序,所以取出的前k个元素就是符合条件的酒店价格。
  5. 输出结果

    • 将筛选出的酒店价格按升序打印出来。

十一、运行步骤

  1. 初始化优先队列。

  2. 遍历价格数组[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个)
  3. 从优先队列中取出前5个元素:

    • 6
    • 5
    • 7
    • 4
    • 8
  4. 打印输出结果:

    4 5 6 7 8
    

十二、结论

对于给定的输入,程序将正确地筛选出最接近心理价位6的5个酒店价格,并按升序打印出来。输出结果为4 5 6 7 8,与预期相符。

上一篇:无人农场解决方案综述


下一篇:Redis之持久化机制和实现原理