在一個巨大的存儲空間

搜索空閒位置的實際問題是：你會使用什麼數據結構，找到一個停車場免費停車位有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

在一個巨大的存儲空間

回答

相關問題