2014-09-26 84 views
1

給定一組條目,每個包含一個時間索引和INT計數值, 即 類條目 { 時間:整數 計數:整數 }查找總計數最高的間隔?

編寫一個函數,將給予的時間間隔最高計數在一起,

即 如果我們有條目

100, 2 
100, 1 
110, 10 
200, 4 
1000, 3 
1200, 8 

,我們跑了類似

int highestInterval(int interval_range) 
highestInterval(50) 

它會返回100,因爲在100-150,你數2,1,和10

我得到了一個O代表它(N^2)的解決方案,但我認爲這是一個更好的解決方案。我認爲這可能與間隔桶的預處理有關,但我無法弄清楚解決方案。

+0

爲了這個,我認爲簡單的循環爲O(n)。我不會發布代碼,因爲它似乎是howework =) – Hotted24 2014-09-26 08:28:43

回答

0

看來你已經使用了兩個for循環,所以它只是一個改進的問題。

這裏去一個可能的解決方案:

CODE:

raw_data=[100,2; 
100,1; 
110,10; 
200,4; 
1000,3; 
1200,8]; 
[max_val,indx]=max(cell2mat(arrayfun(@(A) sum(raw_data(abs(raw_data(A,1)-raw_data(:,1))<50,2)),1:size(raw_data,1),'UniformOutput',false))); 
raw_data(indx,1) 

OUTPUT:

ans = 

    100