monnand
BAN USERclass Island:
def __init__(self, minv, maxv):
self._min = minv
self._max = maxv
def find_missing_positive(array):
islandmap = {}
min_island = Island(0, 0)
for n in array:
if islandmap.has_key(n):
continue
left = None
island = Island(n, n)
if n > 1:
left = islandmap.get(n-1)
if left is not None:
island._min = left._min
right = islandmap.get(n+1)
if right is not None:
island._max = right._max
if min_island._max == 0 or min_island._min >= island._min:
min_island._max = island._max
min_island._min = island._min
islandmap[n] = island
islandmap[island._min] = island
islandmap[island._max] = island
if min_island._min > 1:
return 1
return min_island._max + 1
Sorry, the previous code is wrong
- monnand April 09, 2011<pre lang="" line="1" title="CodeMonkey66871" class="run-this"># In python:
class Island:
def __init__(self, minv, maxv):
self._min = minv
self._max = maxv
def find_missing_positive(array):
islandmap = {}
min_island = Island(0, 0)
for n in array:
if islandmap.has_key(n):
continue
left = None
island = Island(n, n)
if n > 1:
left = islandmap.get(n-1)
if left is not None:
island._min = left._min
right = islandmap.get(n+1)
if right is not None:
right._min = island._min
island._max = right._max
if left is not None:
left._max = island._max
if min_island._max == 0 or min_island._min >= island._min:
min_island._max = island._max
min_island._min = island._min
islandmap[n] = island
if min_island._min > 1:
return 1
return min_island._max + 1
</pre>
<pre lang="" line="1" title="CodeMonkey27155" class="run-this">def markitem(array, i):
- monnand April 09, 2011array[i] = -abs(array[i])
def decodeitem(array, i):
return abs(array[i])
def ismarked(array, i):
return array[i] < 0
def findfirstrep(array):
for i in xrange(len(array)):
n = decodeitem(array, i)
if ismarked(array, n):
return n
markitem(array, n)
if __name__ == "__main__":
a = [10,9,9,7,6,5,4,3,2,1,1]
print findfirstrep(a)
</pre>