5
\$\begingroup\$

Here is a problem I am trying to solve: trying to find missing photographs from a sequence of filenames. The problem boils down to: given an unsorted list of integers, return a sorted list of missing numbers. Below is my code.

What I am looking for are:

  • Are there more efficient algorithms?
  • Is there any performance problem if the list is large (tens of thousands)
  • Corner cases which does not work?

    def find_missing_items(int_list):
        '''
        Finds missing integer within an unsorted list and return a list of 
        missing items
    
        >>> find_missing_items([1, 2, 5, 6, 7, 10])
        [3, 4, 8, 9]
    
        >>> find_missing_items([3, 1, 2])
        []
        '''
    
        # Put the list in a set, find smallest and largest items
        original_set  = set(int_list)
        smallest_item = min(original_set)
        largest_item  = max(original_set)
    
        # Create a super set of all items from smallest to largest
        full_set = set(xrange(smallest_item, largest_item + 1))
    
        # Missing items are the ones that are in the full_set, but not in
        # the original_set
        return sorted(list(full_set - original_set))
    
    if __name__ == '__main__':
        import doctest
        doctest.testmod()
    
\$\endgroup\$
  • \$\begingroup\$ Looks fine to me. find_missing_items([-20000,0,20000]) returned correctly all 39998 items in less than 2s running on a old dual-core. \$\endgroup\$ – Alex Mar 29 '13 at 23:56
6
\$\begingroup\$

For this

full_set = set(xrange(smallest_item, largest_item + 1))

I'd suggest inlining the min and max:

full_set = set(xrange(min(original), max(original) + 1))

You don't need to convert to a list before using sorted so:

sorted(list(full_set - original_set))

Can be written as:

sorted(full_set - original_set)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Beautiful. I especially like the last one: sorted() without list(). \$\endgroup\$ – Hai Vu Mar 30 '13 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.