對於每個元素A [i]於陣列A的，找到最接近Ĵ使得A [J]> A [I]

鑑於：實數的數組A[1..n]。對於每個元素A [i]於陣列A的，找到最接近Ĵ使得A [J]> A [I]

目標：數組D[1..n]使得

D[i] = min{ distance(i,j) : A[j] > A[i] }

或一些默認值（如0）當不存在更高值元素。我真的很想在這裏使用歐幾里德距離。

例：

A = [-1.35, 3.03, 0.73, -0.06, 0.71, -0.21, -0.12, 1.49, 1.41, 1.42] 
D = [1, 0, 1, 1, 2, 1, 1, 6, 1, 2]

是否有任何方式打敗明顯O（n^2）溶液？我迄今取得的唯一進展是D[i] = 1，只要A[i]不是本地最大值。我一直在想很多，並沒有提出什麼。我希望最終擴展到2D（所以A和D是矩陣）。

來源

2010-03-31 SamH

你的符號很好很簡潔，但如果你用英文解釋的話，它可能會更有用（你可能會得到更多的答案）。 – noah 2010-03-31 20:08:24

需要'家庭作業'標籤？ – 2010-03-31 21:08:31

noah：謝謝！我試圖用較少的符號來書寫標題，但是當我將它呈現給坐在我旁邊的兩個人時，他們不喜歡它。我能想到的最好的結果是「在數組的每個元素上，找到最接近數組的元素。」 Paul R：這實際上是我正在研究的一個更大項目中的一小部分，這不是作業。但你是對的，它看起來像功課。 – SamH 2010-03-31 21:32:04

所以我對這一點感到困惑，但我還沒有拿出任何更好的作品。一些想法：

增加陣列與額外的信息，可以在O（n）時間或更好的時間獲得。例如添加索引，鄰國之間的差異等
將排序（O（N（log n）的）幫助以任何方式？
好像dynamic programming可幫助在這裏，如果你能想出一個辦法來解決基於其鄰居溶液（增強的答案與像j每個A[i]，而不是僅僅是可能的距離信息）的每個元素。

來源

2010-04-01 14:23:43 noah

謝謝，我以前沒有想到你的第一個建議。如果我想出任何東西，我肯定會更新此頁面！ – SamH 2010-04-02 19:38:04

排序從高到低排列，以最低的元素。如果我理解你的問題正確的，這會立即給你答案，因爲原始列表中任何元素的最接近的更大的元素是它之前的元素，這樣你甚至不需要c reate D []數組，因爲其內容的計算可以專門用數組A []完成。排序後的A []數組中的第一個元素沒有更大的朋友，所以它的答案應該是默認的valye（0也許是？）。擴展矩陣算法可能很容易（取決於你如何「看待」矩陣） - 只需使用映射函數將矩陣轉換爲一維數組即可。

來源

2010-05-27 06:01:07 PeterK

對於每個元素A [i]於陣列A的，找到最接近Ĵ使得A [J]> A [I]

回答

相關問題