I have an alternative algorithm to the same problem as Finding missing items in an int list.
My implementation includes optional min and max bounds to selectively fill in the list.
The linked implementation is much simpler.
My Questions are:
How do our two algorithms compare, efficiency wise?
Besides the algorithm linked, are there more efficient algorithms?
Did I identify and does my algorithm work for the edge cases?
I tried not to use min
and max
because I heard that they are \$\mathcal{O}(n)\$.
However, I used the .index
method for lists. I am not sure how efficient .index
is. I would think that it would be \$\mathcal{O}(\log n)\$ for a sorted but I am not sure if or how the .index
function would know that a given list is sorted.
Additionally, I used exceptions, which do give a performance penalty.
7 Cases
One missing number - Normal
Multiple Missing Numbers - Normal
No missing numbers - Normal
Repeats - Normal
Array too small - Case for empty array: returns an array of the numbers from
min_val
tomax_val
inclusiveMissing numbers at end - Filled in based on the min and max number
Numbers out of range - Ignored those which were out of range
from bisect import bisect_left
def find_missing(int_array, min_val = False, max_val = False):
"""Doctest
>>> find_missing([1,2,3,5,6,7], 1, 7)
[4]
>>> find_missing([2,3,6,4,8], 2, 8)
[5, 7]
>>> find_missing([1,2,3,4], 1, 4)
[]
>>> find_missing([11,1,1,2,3,2,3,2,3,2,4,5,6,7,8,9],1,11)
[10]
>>> find_missing([-1,0,1,3,7,20], -1, 7)
[2, 4, 5, 6]
>>> find_missing([-2,0,3], -5, 2)
[-5, -4, -3, -1, 1, 2]
>>> find_missing([2],4,5)
[4, 5]
>>> find_missing([3,5,6,7,8], -3, 5)
[-3, -2, -1, 0, 1, 2, 4]
>>> find_missing([1,2,4])
[3]
"""
if len(int_array) == 0:
return list(range(min_val, max_val+1))
int_array = sorted(int_array)
first_in_int_array = int_array[0]
last_in_int_array = int_array[len(int_array)-1]
if not min_val:
min_val = first_in_int_array
if not max_val:
max_val = last_in_int_array
result = []
#Checking to see if the min & max values currently exist
#If they do not then add them to the resultant array as they are missing numbers
if min_val < first_in_int_array:
int_array.insert(0, min_val)
result.append(min_val)
if max_val > last_in_int_array:
int_array.insert(len(int_array), max_val)
result.append(max_val)
#Dealing with case where max_val < last_in_int_array but not in array
#Example: max_val = 2 int_array = [1,3]
#Also dealing with the analogous case for min_val and first_in_int_array
#Deal with this using exceptions
try:
min_pos = int_array.index(min_val)
except Exception as e:
result.append(min_val)
min_pos = bisect_left(int_array, min_val)
int_array.insert(min_pos, min_val)
try:
max_pos = int_array.index(max_val)
except Exception as e:
result.append(max_val)
max_pos = bisect_left(int_array, max_val)
int_array.insert(max_pos, max_val)
for i in range(min_pos,max_pos):
difference = int_array[i+1] - int_array[i]
if difference != 1 and difference != 0:
result += range(int_array[i]+1,int_array[i+1])
result.sort()
return result
except
clause after your firsttry
block. And your whole function isn't indented but that's probably not your fault. \$\endgroup\$