尋找最近的時間爲k空組

最近我在一次採訪中被問到這個問題，我仍然無法想出一個解決方案。尋找最近的時間爲k空組

有在河N個時隙。給出一個數組P，其中每個索引表示該位置處的石頭將出現的時間。我不得不想出一個算法來找到最早的時間，在這個時間點將有K個連續的空插槽。對於E.G.

N = 5 

P = [2,5,1,4,3] 

K = 2 

Initially: [0,0,0,0,0] 

All the slots are empty. 

Now at: 

Time t = 1, second stone will appear --> [0,1,0,0,0] 

Time t = 2, fifth stone will appear --> [0,1,**0,0**,1] 

Time t = 3, first stone will appear --> [1,1,0,0,1] 

Time t = 4, fourth stone will appear --> [1,1,0,1,1] 

Time t = 5, third stone will appear --> [1,1,1,1,1]

因此，對於上面的情況下，答案是2，因爲在時間2有（K = 2）的連續空時隙。

來源

2017-09-24 Shubham

那麼究竟是什麼問題？ – timmyRS

要找出K個連續空槽的最早時間 – Shubham

這將是'2'，就像您在問題中已經寫過的一樣。 – timmyRS

我終於在leetcode上找到了O（n）時間複雜度和O（n）空間複雜度解決方案。先簡單介紹一下：

的想法是使用數組days[]記錄每個位置花的綻放一天。這意味着days[i]是位置i+1中花朵盛開的一天。我們只需要找到一個滿足以下條件的子陣列days[left, left+1,...,left+k-1, right]：對於任何i = left+1,..., left+k-1，我們可以有days[left] < days[i] && days[right] < days[i]。然後，結果是max(days[left], days[right])。

這裏是鏈接到精確解：https://discuss.leetcode.com/topic/104771/java-c-simple-o-n-solution

來源

2017-09-25 21:43:17 Shubham

你可以使用BIT樹來解決這個問題。你需要確切的k個插槽爲空所以我們假設發生在i時刻。

a=p[i]-k-1; 
b=p[i]+k+1;

數組T表示石頭是否在索引i處。

現在指數a和p [I]或B和P之間的所有條目[i]於陣列T應該是零。這可以通過使用範圍查詢來檢查，我更喜歡BIT樹，但也可以使用段樹。

來源

2017-09-24 19:39:46

注意，在內部閉環P項目的i立場的權利可以被安全地忽略。然而，這仍然是爲O（n^2）

int K = 2; 
    int[] P = { 2, 5, 1, 4, 3 }; 
    int N = P.Length; 

    for (int i = 0; i < N; i++) 
    { 
     for (int j = 0; j <= i; j++) 
     { 
      if (Math.Abs(P[j] - P[i] + 1) == K) 
      { 
       return i + 1; //+1 because we iterate from 0 | this is the ans (time) 
      } 

     } 
    }

來源

2017-09-24 19:54:26 Kostya

每次兩個部分加一塊石頭你基本上將連續的空槽（零）的序列。你可以使用這個想法來構建一個二叉樹，其中每個節點代表（零和一 - 石頭和空的空間）的間隔和每個葉節點代表零隻有的間隔。

要添加您找到合適的葉節點（對應時間間隔必須包括新石的位置），並添加新的葉子節點石頭 - 左側和右側VS添加石頭間隔。此時，您可以檢查這些新時間間隔的長度，如果找到具有所需長度的時間間隔，請停止。

唯一這裏的問題是，這棵樹可能變得不平衡，從而獲得O（nlogn），你應該運用一些工藝來平衡樹因爲它的增長最壞的情況 - 紅黑樹或類似的東西 - https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

來源

2017-09-24 21:17:25 algrid

尋找最近的時間爲k空組

回答

相關問題