Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def longest_consecutive_subsequence(input_list):
- """
- Gets the longest sequential (consecutive set of numbers from the given unsorted list.
- Time complexity is O(n) and space complexity is O(n).
- This design uses Python's `range()` function to generate the list of sequential numbers. To accomplish this,
- we iterate through the input list to find the least starting number and the number of sequential numbers.
- It works on all integers.
- :param input_list: given unsorted list of integers (positive and/or negative).
- :return: returns a list of the longest sequential numbers.
- """
- # Create a dictionary where number: visited.
- # Value of 1 means the number has been visited (processed).
- nums = {num: 0 for num in input_list} # O(n)
- current_start = None
- current_count = 0
- longest_start = None
- longest_count = 0
- for num in input_list: # O(n)
- current_count = 1
- current_start = num
- nums[num] = -1
- # Check sequential n + 1.
- current = num + 1
- while current in nums and nums[current] == 0:
- current_count += 1
- nums[current] = 1 # Mark that this number has been visited.
- current += 1
- # Check sequential n - 1.
- current = num - 1
- while current in nums and nums[current] == 0:
- current_start = current
- current_count += 1
- nums[current] = 1 # Mark that this number has been visited.
- current -= 1
- if current_count == longest_count and current_start > longest_start:
- continue
- if current_count >= longest_count:
- longest_start = current_start
- longest_count = current_count
- return [num for num in range(longest_start, longest_start + longest_count)]
- if __name__ == '__main__':
- test_case = [
- [[5, 4, 7, 10, 1, 3, 55, 2], [1, 2, 3, 4, 5]],
- [[2, 12, 9, 16, 10, 5, 3, 20, 25, 11, 1, 8, 6], [8, 9, 10, 11, 12]],
- [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4]],
- [[25, 35, 45, 12, 26, 36, 13, 24, 44, 23], [23, 24, 25, 26]],
- [[0, -1, -2, -3, -10, 20, 30, -4], [-4, -3, -2, -1, 0]]
- ]
- for input, expected in test_case:
- actual = longest_consecutive_subsequence(input)
- if actual == expected:
- print("Passed")
- else:
- print("Failed. actual {} vs. expected {}".format(actual, expected)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement