找到一個輸入數字，知道它應該在陣列中的位置

我有一個小算法問題。例如，我有一個數組。找到一個輸入數字，知道它應該在陣列中的位置

array[10] = {23,54,10,63,52,36,41,7,20,22};

現在給出一個輸入數字，例如189我想知道在哪個槽中應該說謊。例如該輸入應位於4個索引數組中，因爲

23+54+10+63 = 150 and if we add 52 then sum will be 202 which will cover the range where 189 should lie. so the answer should be 4.

我想找到一個固定的時間裏算法可以在我們做一些討人喜歡的陣列上的第一步，使所有的未來我們可以在不斷的時間獲得查詢。

輸入數總是會在1和所有條目的總和之間的陣列
由於

來源

2012-11-01 Madu

你將不會得到分期常量時間爲任一插槽計算或項目插入。據我所知。你期望能夠嗎？ – Rook

自然解決辦法是首先建立與所述累計總和的陣列。這看起來像

sums[10] = {23,77,87,...}

然後使用二進制搜索，如lower_bound算法來找到插入的位置。那將是O(log(n))。假設你的槽數是恆定的，這個解決方案也是時間常數。但我想你想要的插槽數爲O(1)。在這種情況下，您必須創建一個完整的查找表。因爲這些數字的規模比較小，這是完全可行的：

int lookup[N]; 
for(i=0,j=0;i<10;i++) 
    for(k=0;k<sums[i];k++,j++) 
     lookup[j]=i;

利用這一點，插槽數量簡直是lookup[number]。

來源

2012-11-01 13:37:09 amaurea

你是對的，除了他要求恆定的時間。 – Bitwise

對此稍作修改，您可以改爲包含與數組中所有值的總和相同數量的元素（在本例中爲328）的數組。例如，數組中的每個項目的值對應於數組插槽...''lookup [189]'和'lookup [200]'都將具有值'4'。這將受到數組中值總和的嚴格限制，但是對於OP的例子，它可以很容易地作爲O（1）查找工作。 – Rook

@Rook：我想這正是我在這裏所做的。 – amaurea

我認爲你可以得到的最好的結果是使用累積數組並使用二進制搜索在對數時間運行。我不確定是否存在具有恆定時間的解決方案。你確定有嗎？

來源

2012-11-01 13:38:29 ISTB

我不確定是否存在一個。但我真的很感興趣，如果這是爲什麼問社區成員。 – Madu

我認爲它不存在。因爲您將擁有一組帶有「洞」的值，您將需要在此數組中搜索以找到您的位置。並且這個搜索不能在O（1） – ISTB

如果您確實需要一定的時間，請創建第二個數組，該數組的大小是包含索引的最大總和值。所以new_array [189] = 4;

來源

2012-11-01 13:41:23

如果你知道數字總是在1和數組中所有項目的總和之間，那麼平凡的常量時間算法是建立一個[1..sum]的數組，每個條目包含適當的時隙每個號碼。建立一個你只需要做一次的數組就是O（N）。查找是O（1）。

這當然假設你有足夠的內存來存放數組。

除此之外，我認爲你可以做的最好的是O（log（N））使用二進制搜索的總和。

來源

2012-11-01 13:42:58

假設

輸入數總是會在1和所有的條目的總和之間的陣列

int total(0), i(0); 
for(;total < inputValue; ++i) 
{ 
    total += array[i]; 
} 
//your answer is i-1

來源

2012-11-01 13:45:00 Ian

中完成，而運行時間取決於數量。他正在尋找更高效的算法。 –

@jim它在我的腦海中添加了「int answer（i）; for（; i <10; ++ i）{total + = array [i];}」，以使它在常量時間內運行：P – Ian

找到一個輸入數字，知道它應該在陣列中的位置

回答

相關問題