列表

详情

1847. 最近的房间

一个酒店里有 n 个房间，这些房间用二维整数数组 rooms 表示，其中 rooms[i] = [roomIdi, sizei] 表示有一个房间号为 roomIdi 的房间且它的面积为 sizei 。每一个房间号 roomIdi 保证是 独一无二 的。

同时给你 k 个查询，用二维数组 queries 表示，其中 queries[j] = [preferredj, minSizej] 。第 j 个查询的答案是满足如下条件的房间 id ：

如果差的绝对值有 相等 的，选择 最小 的 id 。如果 没有满足条件的房间 ，答案为 -1 。

请你返回长度为 k 的数组 answer ，其中 answer[j] 为第 j 个查询的结果。

 

示例 1：

输入：rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
输出：[3,-1,3]
解释：查询的答案如下：
查询 [3,1] ：房间 3 的面积为 2 ，大于等于 1 ，且号码是最接近 3 的，为 abs(3 - 3) = 0 ，所以答案为 3 。
查询 [3,3] ：没有房间的面积至少为 3 ，所以答案为 -1 。
查询 [5,2] ：房间 3 的面积为 2 ，大于等于 2 ，且号码是最接近 5 的，为 abs(3 - 5) = 2 ，所以答案为 3 。

示例 2：

输入：rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
输出：[2,1,3]
解释：查询的答案如下：
查询 [2,3] ：房间 2 的面积为 3 ，大于等于 3 ，且号码是最接近的，为 abs(2 - 2) = 0 ，所以答案为 2 。
查询 [2,4] ：房间 1 和 3 的面积都至少为 4 ，答案为 1 因为它房间编号更小。
查询 [2,5] ：房间 3 是唯一面积大于等于 5 的，所以答案为 3 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) { } };

rust 解法, 执行用时: 64 ms, 内存消耗: 8.7 MB, 提交时间: 2023-10-08 17:54:07 

use std::collections::BTreeSet;
impl Solution {
    pub fn closest_room(mut rooms: Vec<Vec<i32>>, mut queries: Vec<Vec<i32>>) -> Vec<i32> {
        rooms.sort_unstable_by_key(|x| x[1]);
        for (pos, query) in queries.iter_mut().enumerate() {
            query.push(pos as i32);
        }
        queries.sort_unstable_by_key(|x| x[1]);
        let mut set = BTreeSet::new();
        let mut res = vec![-1; queries.len()];
        while queries.len() > 0 {
            while rooms.len() > 0 && rooms[rooms.len() - 1][1] >= queries[queries.len() - 1][1] {
                set.insert(rooms.pop().unwrap()[0]);
            }
            let pos = queries.last().unwrap()[2] as usize;
            let prefer = queries.pop().unwrap()[0];
            res[pos] = match (set.range(prefer..).next(), set.range(..prefer).last()) {
                (Some(&solu1), Some(&solu2)) => if (solu2 - prefer).abs() <= (solu1 - prefer).abs() {
                        solu2
                    } else {
                        solu1
                    },
                (Some(&solu1), None) => solu1,
                (None, Some(&solu2)) => solu2,
                (None, None) => -1
            }
        }
        res
    }
}

golang 解法, 执行用时: 296 ms, 内存消耗: 23.6 MB, 提交时间: 2023-10-08 17:53:39 

import (
	"math/rand"
)
type node struct {
	Ch       [2]*node
	priority int
	Val      int
}
func (o *node) cmp(b int) int {
	switch {
	case b < o.Val:
		return 0
	case b > o.Val:
		return 1
	default:
		return -1
	}
}

func (o *node) rotate(d int) *node {
	x := o.Ch[d^1]
	o.Ch[d^1] = x.Ch[d]
	x.Ch[d] = o
	return x
}

type Treap struct {
	root *node
}

func (t *Treap) _put(o *node, val int) *node {
	if o == nil {
		return &node{priority: rand.Int(), Val: val}
	}
	d := o.cmp(val)
	o.Ch[d] = t._put(o.Ch[d], val)
	if o.Ch[d].priority > o.priority {
		o = o.rotate(d ^ 1)
	}
	return o
}

func (t *Treap) Put(val int) {
	t.root = t._put(t.root, val)
}

func (t *Treap) _delete(o *node, val int) *node {
	if d := o.cmp(val); d >= 0 {
		o.Ch[d] = t._delete(o.Ch[d], val)
		return o
	}
	if o.Ch[1] == nil {
		return o.Ch[0]
	}
	if o.Ch[0] == nil {
		return o.Ch[1]
	}
	d := 0
	if o.Ch[0].priority > o.Ch[1].priority {
		d = 1
	}
	o = o.rotate(d)
	o.Ch[d] = t._delete(o.Ch[d], val)
	return o
}

func (t *Treap) Delete(val int) {
	t.root = t._delete(t.root, val)
}

func (t *Treap) LowerBound(val int) (lb *node) {
	for o := t.root; o != nil; {
		switch c := o.cmp(val); {
		case c == 0:
			lb = o
			o = o.Ch[0]
		case c > 0:
			o = o.Ch[1]
		default:
			return o
		}
	}
	return
}
func (t *Treap) HighBound(val int) (lb *node) {
	for o := t.root; o != nil; {
		switch c := o.cmp(val); {
		case c == 0:
			o = o.Ch[0]
		case c > 0:
			lb = o
			o = o.Ch[1]
		default:
			return o
		}
	}
	return
}
func closestRoom(rooms [][]int, queries [][]int) []int {
	ans := make([]int, len(queries))
	q := make([][]int, len(queries))
	set:= &Treap{}
	for i := 0; i < len(queries); i++ {
		q[i] = append(queries[i], i)
	}
	sort.Slice(rooms, func(i, j int) bool {
		return rooms[i][1] > rooms[j][1]
	})
	sort.Slice(q, func(i, j int) bool {
		return q[i][1] > q[j][1]
	})
	j:=0
	for i := 0; i < len(q); i++ {
		for j< len(rooms) && rooms[j][1] >= q[i][1] {
			set.Put(rooms[j][0])
			j++
		}
		if j ==0{
			ans[q[i][2]]=-1
			continue
		}
		hb := set.LowerBound(q[i][0])
		if hb!=nil && hb.Val == q[i][0]{
			ans[q[i][2]]=hb.Val
			continue
		}
		lb := set.HighBound(q[i][0])
        // fmt.Println(lb,hb)
		if lb ==nil || (hb!=nil && q[i][0]-lb.Val > hb.Val-q[i][0]){
			ans[q[i][2]]=hb.Val
		}else {
			ans[q[i][2]]=lb.Val
		}
	}
	return ans
}

java 解法, 执行用时: 98 ms, 内存消耗: 84.1 MB, 提交时间: 2023-10-08 17:53:01 

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        // 按房间大小排序
        Arrays.sort(rooms,(a,b)->b[1]-a[1]);
        List<int[]> list = new ArrayList<>();
        int roomCap = rooms.length, querySize = queries.length;
        for (int i=0;i<querySize;i++){
            list.add(new int[]{i,queries[i][0],queries[i][1]});
        }
        // 按最小大小排序
        Collections.sort(list,(a,b)->b[2]-a[2]);
        TreeSet<Integer> roomIds = new TreeSet<>();
        int[] res = new int[querySize];
        int idx = 0;
        for (int[] query : list) {
            int pos = query[0], preferred = query[1], minSize = query[2];
            // 维护符合要求的房间id
            while (idx<roomCap && rooms[idx][1]>=minSize){
                roomIds.add(rooms[idx][0]);
                idx++;
            }
            // 获取请求结果
            if (roomIds.isEmpty()) res[pos] = -1;
            else {
                Integer ceiling = roomIds.ceiling(preferred);
                Integer floor = roomIds.floor(preferred);
                if (ceiling==null) res[pos]=floor;
                else if (floor==null) res[pos]=ceiling;
                else res[pos] = preferred-floor<=ceiling-preferred ? floor : ceiling;
            }
        }
        return res;
    }
}

python3 解法, 执行用时: 1276 ms, 内存消耗: 64.9 MB, 提交时间: 2023-10-08 17:52:47 

class Event:
    """
    op: 事件的类型，0 表示房间，1 表示询问
    size: 房间的 size 或者询问的 minSize
    idx: 房间的 roomId 或者询问的 preferred
    origin: 房间在数组 room 中的原始编号或者询问在数组 queries 中的原始编号
    """
    def __init__(self, op: int, size: int, idx: int, origin: int):
        self.op = op
        self.size = size
        self.idx = idx
        self.origin = origin

    """
    自定义比较函数，按照事件的 size 降序排序
    如果 size 相同，优先考虑房间
    """
    def __lt__(self, other: "Event") -> bool:
        return self.size > other.size or (self.size == other.size and self.op < other.op)

class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        import sortedcontainers
        
        n = len(queries)

        events = list()
        for i, (roomId, size) in enumerate(rooms):
            # 房间事件
            events.append(Event(0, size, roomId, i))

        for i, (minSize, preferred) in enumerate(queries):
            # 询问事件
            events.append(Event(1, preferred, minSize, i))

        events.sort()

        ans = [-1] * n
        # 存储房间 roomId 的有序集合
        # 需要导入 sortedcontainers 库
        valid = sortedcontainers.SortedList()
        for event in events:
            if event.op == 0:
                # 房间事件，将 roomId 加入有序集合
                valid.add(event.idx)
            else:
                # 询问事件
                dist = float("inf")
                # 查找最小的大于等于 preferred 的元素
                x = valid.bisect_left(event.idx)
                if x != len(valid) and valid[x] - event.idx < dist:
                    dist = valid[x] - event.idx
                    ans[event.origin] = valid[x]
                if x != 0:
                    # 查找最大的严格小于 preferred 的元素
                    x -= 1
                    if event.idx - valid[x] <= dist:
                        dist = event.idx - valid[x]
                        ans[event.origin] = valid[x]
            
        return ans

cpp 解法, 执行用时: 588 ms, 内存消耗: 183.1 MB, 提交时间: 2023-10-08 17:51:34 

struct Event {
    // 事件的类型，0 表示房间，1 表示询问
    int type;
    // 房间的 size 或者询问的 minSize
    int size;
    // 房间的 roomId 或者询问的 preferred
    int id;
    // 房间在数组 room 中的原始编号或者询问在数组 queries 中的原始编号
    int origin;
    
    Event(int _type, int _size, int _id, int _origin): type(_type), size(_size), id(_id), origin(_origin) {}
    
    // 自定义比较函数，按照事件的 size 降序排序
    // 如果 size 相同，优先考虑房间
    bool operator< (const Event& that) const {
        return size > that.size || (size == that.size && type < that.type);
    }
};

class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        int m = rooms.size();
        int n = queries.size();
        
        vector<Event> events;
        for (int i = 0; i < m; ++i) {
            // 房间事件
            events.emplace_back(0, rooms[i][1], rooms[i][0], i);
        }
        for (int i = 0; i < n; ++i) {
            // 询问事件
            events.emplace_back(1, queries[i][1], queries[i][0], i);
        }

        sort(events.begin(), events.end());
        
        vector<int> ans(n, -1);
        // 存储房间 roomId 的有序集合
        set<int> valid;
        for (const auto& event: events) {
            if (event.type == 0) {
                // 房间事件，将 roomId 加入有序集合
                valid.insert(event.id);
            }
            else {
                // 询问事件
                int dist = INT_MAX;
                // 查找最小的大于等于 preferred 的元素
                auto it = valid.lower_bound(event.id);
                if (it != valid.end() && *it - event.id < dist) {
                    dist = *it - event.id;
                    ans[event.origin] = *it;
                }
                if (it != valid.begin()) {
                    // 查找最大的严格小于 preferred 的元素
                    it = prev(it);
                    if (event.id - *it <= dist) {
                        dist = event.id - *it;
                        ans[event.origin] = *it;
                    }
                }
            }
        }
        
        return ans;
    }
};

上一题

© 2024 leetcode.cn