在一个巨大的存储空间

搜索空闲位置的实际问题是：你会使用什么数据结构，找到一个停车场免费停车位有600万点？在一个巨大的存储空间

我的想法：

我可以用一个LinkedHashMap和保持运动的自由点到队列的前面，但我不认为这是正确的解决方案。

有什么想法？

2012-03-29 noMAD

您是否在意寻找最近的地点或所有“免费停车位”？车库是多层次的吗？与在这个水平上进一步开车相比，你如何确定上升到下一个水平的成本？这些都是您在考虑解决方案时可能会问的所有问题。 – Seph 2012-03-29 11:29:33

一个简单的解决方案将维护所有停车位的静态数组和免费地点的链接列表。首先所有景点都在免费链接列表中。当停车请求到达时，您返回链接列表的头部并将其从中移除，并将其标记在数组中。当一个点释放时，将其添加到链表（将其标记为数组）。 – 2012-03-29 17:24:12

PriorityQueue优先级定义为停车位和入口之间的距离。

来源

2012-03-29 04:36:35 iehrlich

'LinkedHashMap'使用一个优先级队列。但是你不能在队列中存储一百万个节点。至少这是我的想法。 – noMAD 2012-03-29 04:44:41

你为什么这么认为？ – iehrlich 2012-03-29 04:46:20

我会使用一个位集，其中每个位代表一个停车位。值1为免费，0为已使用。线性搜索免费景点应该能够胜任这项工作。很容易实现，而且速度足够快。

来源

2012-03-29 07:15:32 knivil

您已经知道您的停车结构的大小（一百万个插槽），这在物理上有意义。所以，如果你需要的信息很多是空的，然后使用一个位阵列，其中空置是假的，并占领如果您需要存储更多的信息，比如在汽车的信息是真实的

boolean slots[] = new boolean[1000000];

插槽，从最近的入口，等插槽的距离，然后用：

Slot[] slots = new Slot[1000000];

和时隙等级将类似于

public class Slot{ 
    Car car;//object for car in slot 
    boolean occupied;//whether slot is vacant: may be redundant 
    Cost cost;//a set of fields: distance from entrance; parking fee for "good" slots, etc. 
}

所以你坚持下去......

来源

2012-03-29 14:06:19 kasavbere

提高kasavbere的解决方案，我建议使用BitSet/BitArray类，如果你有选择。 BitSet使用long数组，每个long值表示64个时隙。与布尔值 [Arrays of booleans typically occupy 1 byte per element]相比，这有效地将阵列的总大小减少了8倍。 BitSet还提供了从特定索引获取下一个集或空闲插槽的方法，因此您不必为此编写自己的方法。

来源

2012-03-30 19:18:58 Faisal

我们可以使用队列。

该队列在开始时包含所有数百万条目。如果停车空间需要，出队。如果一个停车位变得免费，enque。

来源

2012-03-31 20:17:06 Sandeep

保持一个阵列，基本上可容纳1 - n辆车，其中n是停车场的大小。保持停车场号码的最小堆（PriorityQueue）。每次有新车进场时，检查阵列是否已满，是否轮询最近的批号。轮询从队列中删除最小的并将其用作数组的索引。

一旦汽车离开现场，添加点回到队列。未来民意调查将返回可用的下一个最近的停车场。

来源

2014-04-01 03:01:57 user2100441

在一个巨大的存储空间

回答

相关问题