算法：找出給定範圍內的數字的個數

給定一個未分類的數組數組，其中可以有重複數據，對數組進行預處理，以便查找給定範圍內的數字數，時間爲O（1）。算法：找出給定範圍內的數字的個數

例如，7,2,3,2,4,1,4,6。 >= 2和<= 5的數字計數爲5。 (2,2,3,4,4)。

來源

2011-04-07 user697417

是「預處理」部分O（1）？我不明白這怎麼可能。我猜你的意思是預處理數組，使得結果可以計算O（1）中給定條件的數量？ – 2011-04-07 19:06:16

聽起來像功課嗎？如果是，請給它貼上標籤。 – 2011-04-07 19:14:26

允許的最小/最大範圍是多少？ – 2011-04-07 19:15:52

對數組進行排序。對於排序數組中的每個元素，將該元素插入散列表中，元素的值作爲關鍵字，並將其在數組中的位置作爲關聯值。任何被跳過的值，您都需要插入。

要查找範圍內的項目數量，請在哈希表中查找該範圍每端的值的位置，然後從上面減去該值以查找範圍的大小。

來源

2011-04-07 19:14:26

我只會這樣做，如果輸入數組永遠不稀疏，否則你可能會構造一個非常大的哈希映射。或者將每個元素的個別計數存儲在散列圖中，並檢查範圍中的每個項目。雖然不是O（1）。 – pmr 2011-04-07 19:18:52

該解決方案如何處理原始數組中的重複數字？對於OP的例子，你會如何區分第一個和第二個？ – DShook 2011-04-07 19:31:27

@pmr：是的，如果你的輸入非常稀疏，這將是非常浪費。 @DShook：你會有幾個選擇。兩個明顯的方法是跟蹤第一個和最後一個位置，並跟蹤第一個位置和相同元素的數量。 – 2011-04-07 19:50:26

這聽起來很像一些面試官喜歡問的那些聰明的面試問題中的一個，這些問題通常與提示一路上看到你的想法有關。

無論如何...實現這一目標的一種可能方式是製作一個數目等於或小於列表索引的列表。

例如，從上面的列表中，生成列表：0,1,3,4,6,6,7,8，然後您可以通過從列表中減去列表[1]來計算2到5之間的數字[5]。

來源

2011-04-07 19:15:03 jkerian

即使如此，只有當數字本身來自有限的範圍（例如，如果它們被保證適合於一個普通的int），它纔是O（1）。 – 2011-04-07 19:19:46

要迂腐，如果你的列表類型不適合普通的int，它就不會停止O（1）...它停止完全工作（因爲所需的內存超過許多/大多數系統上的可尋址空間）。但是，該系統可以處理比int大的值。因爲沒有理由生成的count數組不能使用比uint更復雜的東西作爲計數器。 – jkerian 2011-04-07 19:25:21

由於我們需要在O（1）中訪問，所需的數據結構將會佔用大量內存。
隨着哈希表，在最壞的情況下訪問將需要O（N）

我的解決方案：
構建2D矩陣。
array = {2,3,2,4,1,4,6}數字範圍= 0到6所以n = 7
所以我們必須創建nxn矩陣。
陣列[I] [i]表示元素的總計數= I
所以陣列[4] [4] = 2（因爲4出現在陣列2次）
陣列[5] [5] = 0
陣列[5] [2] =數字的計數兩者> = 2和< = 5 = 5

//preprocessing stage 1: Would populate a[i][i] with total count of element = i 
a[n][n]={0}; 
for(i=0;i<=n;i++){ 
    a[i][i]++; 
} 

//stage 2 
for(i=1;i<=n;i++) 
    for(j=0;j<i;j++) 
    a[i][j] = a[i-1][j] + a[i][i]; 
//we are just adding count of element=i to each value in i-1th row and we get ith row.

現在（5,2）將查詢用於[5] [2]和將給出答案爲O （1）

來源

2011-04-13 00:33:39

int main() 
{ 
    int arr[8]={7,2,3,2,4,1,4,6}; 
    int count[9]; 
    int total=0;  

    memset(count,0, sizeof(count)); 

    for(int i=0;i<8;i++) 
     count[arr[i]]++; 

    for(int k=0;k<9;k++) 
    { 
     if(k>=2 && k<=5 && count[k]>0) 
     { 
      total= total+count[k] ;  
     } 
    } 

    printf("%d:",total); 
    return 0; 
}

來源

2017-05-13 13:10:03

算法：找出給定範圍內的數字的個數

回答

相關問題