Last active
October 14, 2019 20:07
-
-
Save airekans/5545009 to your computer and use it in GitHub Desktop.
在一个无序数组里面,找到最长的连续数区间。除了用O(lg n)的排序之外,还有没有O(n)的方法?
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 实际上,下面的解法不是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 file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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