• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
4%
SHARE
TWEET

# finding k missing numbers in a permutation of 0..n-1

hieuza Oct 21st, 2012 706 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python
2. # @ hieuza [x] gmail.com
3.
4. # find k missing numbers in an array of (n - k) elements
5. # the element values are in range 0 .. n-1
6.
7. # complexity: time O(n), space O(k)
8.
9. def find_k_missing(a, n):
10.         if len(a) == n: # not missing any number
11.                 return []
12.
13.         if len(a) == 0: # missing all the number
14.                 return range(n)
15.
16.         a.extend([a[0]]*(n - len(a)))
17.
18.         for i in xrange(n):
19.                 while a[i] != a[a[i]]:
20.                         # swap a[i] and a[a[i]]
21.                         t = a[i]
22.                         a[i] = a[t]
23.                         a[t] = t # always one element is put in correct position
24.
25.         return [i for i in xrange(n) if a[i] != i]
26.
27.
28. def test(n, k):
29.         import random
30.         a = range(n)
31.         random.shuffle(a)
32.         a = a[:n-k]
33.
34.         print 'a:', a
35.         print 'n:', n
36.
37.         res = find_k_missing(a, n)
38.
39.         print '>:', res
40.
41.
42. if __name__ == '__main__':
43.         import sys
44.
45.         n = 5
46.         k = 3
47.
48.         print 'usage: [n] [k]'
49.
50.         if len(sys.argv) > 1:
51.                 n = int(sys.argv[1])
52.
53.         if len(sys.argv) > 2:
54.                 k = int(sys.argv[2])
55.
56.         test(n, k)
RAW Paste Data
Top