Skip to content

Instantly share code, notes, and snippets.

@CNuge
Created March 29, 2018 15:43
Show Gist options
  • Save CNuge/0dfa099a165077e06e4d81e91665e370 to your computer and use it in GitHub Desktop.
Save CNuge/0dfa099a165077e06e4d81e91665e370 to your computer and use it in GitHub Desktop.
# ORIGINAL version
def merge_sorted(list_a, list_b):
""" take two lists of integers sorted smallest to largest,
merge them to a single output list with
no duplicate values """
output_list = []
while (len(list_a) > 0) and (len(list_b) > 0):
if list_a[0] == list_b[0]:
output_list.append(list_a.pop(0))
list_b.pop(0)
elif list_a[0] < list_b[0]:
output_list.append(list_a.pop(0))
elif list_a[0] > list_b[0]:
output_list.append(list_b.pop(0))
if len(list_a) > 0:
output_list.extend(list_a)
elif len(list_b) > 0:
output_list.extend(list_b)
return output_list
# CONSTRAINED version
def constrained_merge_sorted(list_a, list_b):
globals().__setitem__('output_list' , list_a * 0)
while (len(list_a) is not 0) and (len(list_b) is not 0):
if (list_a[0]) is (list_b[0]):
globals().__setitem__('output_list', output_list + [list_a.pop(0)])
list_b.pop(0)
elif abs(list_a[0] - list_b[0]) is not (list_a[0] - list_b[0]):
globals().__setitem__('output_list', output_list + [list_a.pop(0)])
elif abs(list_a[0] - list_b[0]) is (list_a[0] - list_b[0]):
globals().__setitem__('output_list', output_list + [list_b.pop(0)])
if len(list_a) is not 0:
return output_list + list_a
elif len(list_b) is not 0:
return output_list + list_b
else:
return output_list
list_a = [1,3,4,5]
list_b = [2,5,6,7,8]
constrained_merge_sorted(list_a, list_b)
x = [1,2,3,7]
y = [2,3,6,8,9]
merge_sorted(x, y)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment