在2D平面上找到方形邊長是R？

我是在高頻交易公司的採訪，他們問我在2D平面上找到方形邊長是R？

找到一個正方形，其長度尺寸爲R與給定的n個點在2D平面

條件：

--parallel雙方軸和它所包含的n個點

運行的複雜性是不是相對於R 1至少5

他們告訴我給他們爲O（n）algorit hm

來源

2013-03-11 user2149873

那麼你是如何迴應的？ – agentp 2013-03-11 20:04:05

R是提前給你的，還是你被允許選擇它？ – jerry 2013-03-11 20:28:28

這裏必須更加缺少。提出的問題（假設給出R）可能沒有解決方案。 – agentp 2013-03-11 21:07:30

通過設置一次，保持（排序的）本地數組中的5個最大的x值。維護排序後的本地數組是O（N）（恆定時間最多執行N次）。

Y上再次定義XMIN和XMAX作爲兩個點與最大和第五最大的x值分別（即（A [0]和[4]）。

排序一個[]的x座標值，並且在恆定時間設定YMIN與YMAX如上，再次

定義DELTAX = xMax- XMIN，和移動deltaY作爲YMAX - yMin和R =最大DELTAX和移動deltaY的

側的平方。位於右上方（xMax，yMax）處的長度R符合標準。

觀察如果R是固定的預先：

O（N）的複雜性意味着任何排序允許除了在固定數量的點，因爲只有一個基數排序將符合標準和它需要的值的約束沒有提供xMax-xMin和yMax-yMin。
也許訣竅在於從最下方離開的點開始，向上向右移動。最左下角的點可以在輸入的單個路徑中確定。
向上和向右移動，在正方形請求中的步驟和計數點上預先排序X和Y上的點，這要在O（N）時間內完成，要求滿足基數排序約束條件。

來源

2013-03-11 20:05:49

這不起作用。計數器例子：點是{（100,0），（99,1），（99,2），（101,1），（101,2），（0,100），（1,99），（2 ，99），（1101），（2101）}'。然後，ax [0] = ay [0] = 101'，'ax [4] = ay [4] = 99'，'deltaX = 2'和'deltaY = 2'。但是，軸線對齊的邊長爲2的方格的右上角位於'（101,101）'處，不包含任何給定的點。另外，我認爲OP的問題意味着R是提前提供的常數。我會要求澄清。 – jerry 2013-03-11 20:21:50

你可以定義R嗎？我會假設這是一個固定的輸入，否則你可以很容易地把它做得足夠大來覆蓋所有的東西。 – 2013-03-11 20:25:39

@jerry：不要重新選擇y的點，使用最大的x的原始5點，然後在y上使用這5個點。你的例子給出了deltaX = 101-2 = 99，deltaY = 101，R = 101. – 2013-03-11 20:27:40

有趣的問題，感謝發佈！這是我的解決方案。這感覺有點不雅，但我認爲它符合問題的定義：

輸入：R，P = {(x_0, y_0), (x_1, y_1), ..., (x_N-1, y_N-1)}

輸出：(u,v)使得具有角落(u,v)和(u+R, v+R)廣場包含P，或NULL如果至少5個點沒有這樣的(u,v)存在

約束：漸近運行時間應該是O(n)

考慮與平鋪平面正方形。構造一個稀疏矩陣，B定義爲

B[i][j] = {(x,y) in P | floor(x/R) = i and floor(y/R) = j}

當你正在構建B，如果你發現至少包含五個要素停止含五點矩陣條目i,j的進入和輸出(u,v) = (i*R, j*R)。

如果B的構造沒有產生解決方案，那麼要麼沒有解決方案，要麼邊長爲R的平方不符合我們的平鋪。爲了測試第二種情況，我們將考慮來自四個相鄰瓦片的點。

遍歷B中的非空條目。對於每個非空條目B[i][j]，請考慮條目自身所代表的瓦片中包含的點以及上方和右側的瓦片中的點的集合。這些是條目中的點：B[i][j], B[i+1][j], B[i][j+1], B[i+1][j+1]。由於每個條目的數量必須少於5個，因此此集合中的分數不得超過16個。檢查此集合並測試此集合中的點數是否滿足問題標準的5個點數;如果這樣停止並輸出解決方案。（我可以更詳細地指定這個算法，但是因爲（a）這樣的算法明顯存在，並且（b）其漸近運行時間是O(1)，所以我不會詳細討論）。

如果迭代B中的條目後沒有找到解決方案，則輸出NULL。

B的構建只涉及P，因此是O(N)。 B不超過N元素，因此重複它是O(N)。 B中每個元素的算法考慮不超過16個點，因此不依賴於N，因此該總體解決方案符合O(N)目標。

來源

2013-03-12 02:35:10 PaulF

+1 - 你不能跳過空的b [i] [j] - 儘管一個解決方案可能會在空箱子裏留下一個左下角。 – agentp 2013-03-12 12:20:09

@george - 很好的接收！我們可以包含來自B [i-1] [j]，B [i-1] [j + 1]的額外的貼圖來解決這個問題，並且仍然保持我們想要的漸近性能。 – PaulF 2013-03-12 14:25:46

+1昨天晚上我有類似的想法，但你必須小心'B'以確保複雜度既O（n）又獨立於'R'。 'B'可能必須是一個矩形陣列，以便分配和檢查相鄰瓦片的訪問可以在恆定時間內發生。使用初始傳遞來查找邊界，數組將具有「ceil（（maxX-minX）/ R）* ceil（（maxY-minY）/ R）'元素。爲了避免檢查每個點是否爲空，請保留一個未排序的列表，列出n個點中每個點放入哪個圖塊並對其進行迭代。 – jerry 2013-03-12 15:06:09

在2D平面上找到方形邊長是R？

回答

相關問題