有人在幾個星期前發佈了這個問題,但它看起來非常像沒有事先研究的作業,並且OP在得到一些提示後立即將其刪除。計算一組間隔中未涵蓋的最小正整數
這個問題本身是相當有趣的,雖然,我一直在思考了一個星期沒有找到一個令人滿意的解決方案。希望有人能幫忙?
的問題是如下:指定N整數間隔,其範圍可以取任何值從0
到N³
,找到的最小整數i
使得i
不屬於任何輸入間隔的列表。
例如,如果給出列表[3,5] [2,8] [0,3] [10,13]
(N = 4),算法應該返回9
。
我可以在O(n log(n))
認爲運行的最簡單的解決方案,並且包括三個步驟:
- 排序的間隔通過增加下界
-
- 如果最小的下限是> 0,返回0;
- 與第二否則反覆合併所述第一間隔,直到第一時間間隔(比如說
[a, b]
)不接觸所述第二(比方說[c, d]
) - 即,直到B + 1 < c或直到只有一個間隔。
- 返回
b + 1
這種簡單的解決方案運行在O(n log(n))
,但原來的海報中寫道,該算法應O(n)
運行。如果間隔已經排序,那麼這很重要,但OP給出的例子包括未排序的間隔。 我想它一定與N³
綁定有關,但我不確定是什麼......哈希?線性時間排序?想法是受歡迎的。
這裏是上述的算法粗略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到N³的任何值(0而不是1) – Vincent
「恆定時間排序?」有*沒有*這樣的事情。對一系列'n'值進行排序,即使在最好的情況下,也需要'O(n)'時間。您必須至少進行n-1比較來檢查元素是否已排序。 – Bakuriu