#!/usr/bin/env python
# @ hieuza [x] gmail.com
# find k missing numbers in an array of (n - k) elements
# the element values are in range 0 .. n-1
# complexity: time O(n), space O(k)
def find_k_missing(a, n):
if len(a) == n: # not missing any number
return []
if len(a) == 0: # missing all the number
return range(n)
a.extend([a[0]]*(n - len(a)))
for i in xrange(n):
while a[i] != a[a[i]]:
# swap a[i] and a[a[i]]
t = a[i]
a[i] = a[t]
a[t] = t # always one element is put in correct position
return [i for i in xrange(n) if a[i] != i]
def test(n, k):
import random
a = range(n)
random.shuffle(a)
a = a[:n-k]
print 'a:', a
print 'n:', n
res = find_k_missing(a, n)
print '>:', res
if __name__ == '__main__':
import sys
n = 5
k = 3
print 'usage: [n] [k]'
if len(sys.argv) > 1:
n = int(sys.argv[1])
if len(sys.argv) > 2:
k = int(sys.argv[2])
test(n, k)