Skip to content

Instantly share code, notes, and snippets.

@airekans
Last active October 14, 2019 20:07
Show Gist options
  • Save airekans/5545009 to your computer and use it in GitHub Desktop.
Save airekans/5545009 to your computer and use it in GitHub Desktop.
在一个无序数组里面,找到最长的连续数区间。除了用O(lg n)的排序之外,还有没有O(n)的方法?
# 实际上,下面的解法不是O(n),而是O(n + k),其中k是出现数字的区间大小。
def consecutive(numbers):
# get the min and max of the numbers
min, max = None, None
for n in numbers:
if min is None or min > n:
min = n
if max is None or max < n:
max = n
hash_table_length = max - min + 1
hash_table = [False] * hash_table_length
for n in numbers:
hash_table[n - min] = True
beg, end = -1, -2
tmp_beg, tmp_end = -1, -1
i = 0
while (i < hash_table_length):
if hash_table[i]:
tmp_beg, tmp_end = i, i
i += 1
while (i < hash_table_length):
if hash_table[i]:
tmp_end = i
i += 1
else:
break
if tmp_end - tmp_beg > end - beg:
beg, end = tmp_beg, tmp_end
else:
i += 1
return range(beg + min, end + min + 1)
if __name__ == '__main__':
print consecutive([3, 5, 7, 8, 1, 2, 6])
# This is the O(n) solution by using union find set
fathers = None
counts = None
def find_set(x):
if x != fathers[x]:
fathers[x] = find_set(fathers[x])
return fathers[x]
def union(x, y):
fx = find_set(x)
fy = find_set(y)
if fx == fy:
return
elif counts[fx] > counts[fy]:
fathers[fy] = fx
counts[fx] += counts[fy]
else:
fathers[fx] = fy
counts[fy] += counts[fx]
def consecutive(numbers):
# get the min and max of the numbers
global fathers, counts
min, max = None, None
for n in numbers:
if min is None or min > n:
min = n
if max is None or max < n:
max = n
fathers = [n for n in xrange(max + 1)]
counts = [0] * (max + 1)
for n in numbers:
counts[n] += 1
if n - 1 >= 0 and counts[n - 1] > 0:
union(n - 1, n)
if n + 1 <= max and counts[n + 1] > 0:
union(n, n + 1)
max_count, max_index = 0, -1
for n in numbers:
cnt = counts[find_set(n)]
if cnt > max_count:
max_count = cnt
max_index = n
beg_index, end_index = max_index, max_index
while beg_index - 1 >= 0 and counts[beg_index - 1] > 0:
beg_index -= 1
while end_index + 1 <= max and counts[end_index + 1] > 0:
end_index += 1
return range(beg_index, end_index + 1)
if __name__ == '__main__':
print consecutive([3, 5, 7, 8, 1, 2, 6])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment