2013-10-10 40 views
11

有人在幾個星期前發佈了這個問題,但它看起來非常像沒有事先研究的作業,並且OP在得到一些提示後立即將其刪除。計算一組間隔中未涵蓋的最小正整數

這個問題本身是相當有趣的,雖然,我一直在思考了一個星期沒有找到一個令人滿意的解決方案。希望有人能幫忙?

的問題是如下:指定N整數間隔,其範圍可以取任何值從0,找到的最小整數i使得i不屬於任何輸入間隔的列表。

例如,如果給出列表[3,5] [2,8] [0,3] [10,13](N = 4),算法應該返回9

我可以在O(n log(n))認爲運行的最簡單的解決方案,並且包括三個步驟:

  1. 排序的間隔通過增加下界
    • 如果最小的下限是> 0,返回0;
    • 與第二否則反覆合併所述第一間隔,直到第一時間間隔(比如說[a, b])不接觸所述第二(比方說[c, d]) - 即,直到B + 1 < c或直到只有一個間隔。
  2. 返回b + 1

這種簡單的解決方案運行在O(n log(n)),但原來的海報中寫道,該算法應O(n)運行。如果間隔已經排序,那麼這很重要,但OP給出的例子包括未排序的間隔。 我想它一定與綁定有關,但我不確定是什麼......哈希?線性時間排序?想法是受歡迎的。


這裏是上述的算法粗略Python實現:

def merge(first, second): 
    (a, b), (c, d) = first, second 
    if c <= b + 1: 
     return (a, max(b, d)) 
    else: 
     return False 

def smallest_available_integer(intervals): 
    # Sort in reverse order so that push/pop operations are fast 
    intervals.sort(reverse = True) 

    if (intervals == [] or intervals[-1][0] > 0): 
     return 0 

    while len(intervals) > 1: 
     first = intervals.pop() 
     second = intervals.pop() 

     merged = merge(first, second) 
     if merged: 
      print("Merged", first, "with", second, " -> ", merged) 
      intervals.append(merged) 
     else: 
      print(first, "cannot be merged with", second) 
      return first[1] + 1 

print(smallest_available_integer([(3,5), (2,8), (0,3), (10,13)])) 

輸出:

Merged (0, 3) with (2, 8) -> (0, 8) 
Merged (0, 8) with (3, 5) -> (0, 8) 
(0, 8) cannot be merged with (10, 13) 
9 
+0

我假設你的意思是非負整數,只有? –

+0

這似乎是一個錯誤:'誰的邊界可以從0到N³的任何值(0而不是1) – Vincent

+0

「恆定時間排序?」有*沒有*這樣的事情。對一系列'n'值進行排序,即使在最好的情況下,也需要'O(n)'時間。您必須至少進行n-1比較來檢查元素是否已排序。 – Bakuriu

回答

8

在闡述@ MRIP的評論:你可以在O做到這一點(N)通過使用所描述的確切算法,但改變排序算法的工作方式。

通常,基數排序使用基數2:基於它們的位是0還是1,將這些元素分成兩個不同的存儲桶。每一輪基數排序需要時間O(n),並且每一位數量最多。調用最大的nunber U,這意味着時間複雜度爲O(n log U)。

但是,您可以更改基數排序到其他基地的基礎。使用基數b,每輪需要時間O(n + b),因爲需要花費時間O(b)初始化並迭代桶和O(n)時間以將元素分配到桶中。然後有日誌 b U輪。這給出了O((n + b)日誌的運行時間)。

這裏的訣竅在於,由於最大數U = n ,您可以設置b = n並使用基數n基數排序。回合的數量現在是log n U = log n n = 3並且每輪都花費O(n)時間,因此排序數字的總工作量爲O(n)。更一般地說,您可以在任何k的時間O(kn)中對範圍[0,n k)中的數字進行排序。如果k是一個固定的常數,這是O(n)時間。

結合您的原始算法,這解決了問題的時間O(n)。

希望這有助於!

+0

謝謝,這確實是一個非常漂亮的解決方案! –

0

另一個想法是以某種方式使用這些間隔的補充。假設C()給出了一個區間的補數,例如C([3,5])將是小於3的整數和大於5的整數。如果最大數是N^3,則使用模N^3 + 1,你甚至可以把它表示爲另一個區間[6,(N^3 + 1)+2]。

如果你想要一個不屬於任何原始時間間隔的數字,這個時間間隔的所有補數都應該存在相同的數字。然後寫出一個函數來計算任意兩個這樣的「互補間隔」的交集。

我還沒有實現這個想法,因爲我的筆和紙圖表明在計算這樣一個交點時有更多的情況要比我想象的要多。但我認爲這背後的想法是有效的,它會導致O(n)算法。

編輯

在進一步的思考,有最壞的情況下,使事情更加複雜,比我想象的最初。

+0

我不知道你將如何相交線性時間的所有間隔,雖然... –

+0

如果你代表這些補充作爲間隔本身,要找到兩個交集,你必須考慮一些情況來檢查它們如何定位相對於彼此。但是這可以根據它們的開始點和結束點來完成,因此每個交點計算所需的時間量並不取決於輸入的長度。由於您只需處理長度爲N的輸入列表中的每個項目,就會給出一個O(N)複雜度。 – brm

+0

我現在認識到,實際上有一個比我原先想象的更復雜的案例。不完全確定這對複雜性有什麼影響,但它可能不是O(n)了(至少不是我想要做交點的方式) – brm