我要招人

去企业版

首页 > 试题广场 >

数组Mex

[编程题]数组Mex

热度指数：10697 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请设计一个高效算法，查找数组中未出现的最小正整数。

给定一个整数数组A和数组的大小n，请返回数组中未出现的最小正整数。保证数组大小小于等于500。

测试样例：

[-1,2,3,4],4

返回：1

算法知识视频讲解

Python

spongebob7

class ArrayMex:
def findArrayMex(self, A, n):
# write code here
arr = sorted(A)
res = 0
if arr[0]>1:
res=1
else:
for i in range(0,n-1):
if arr[i]>=0 and arr[i+1]-arr[i]>1:
res = arr[i]+1
break
if res==0:
res=arr[-1]+1
return res

发表于 2021-03-28 17:28:21 回复(0)

Python

lx的流星

# -*- coding:utf-8 -*-

class ArrayMex:
    def findArrayMex(self, A, n):
        # write code here
        max_num=max(A)
        for i in range(1,max_num+2):
            if i not in A:
                return i

发表于 2019-07-22 19:48:24 回复(0)

Python

离疏

# -*- coding:utf-8 -*-
class ArrayMex:
    def findArrayMex(self, A, n):
        ans=1
        A=sorted(filter(lambda x:x>0,A))#只保留正整数，并排序
        while ans in A:#若数组中已出现过，则加1
            ans+=1
        return ans

发表于 2018-08-22 11:43:22 回复(0)

Python

华科平凡

python solution easy to understand：

class ArrayMex:
    def findArrayMex(self, A, n):
        test = [False] * (n + 1)
        for i in A:
            if i > 0: test[i] = True
        for i, v in enumerate(test):
            if i > 0 and v == False:
                return i

发表于 2017-09-12 12:08:55 回复(2)

Python

suanfalianxi

# -*- coding:utf-8 -*-

class ArrayMex:

def findArrayMex(self, A, n):

# write code here

if n<=500:

s = []

for i in range(n):

if A[i]<=0:

s.append(A[i])

if len(s)!=0:

for i in range(len(s)):

A.remove(s[i])

A.sort()

A = list(set(A))

if len(A)==0:

return 1

elif len(A)==1:

if A[0]==1:

return A[0]+1

else:

return 1

else:

t = []

tt = []

for i in range(len(A)-1):

if A[i+1]==A[i]+1:

t.append(A[i+1])

else:

tt.append(A[i])

if len(t)==len(A)-1:

if A[0]==1:

return A[len(A)-1]+1

else:

return 1

else:

if A[0]==1:

return tt[0]+1

else:

return 1

发表于 2017-07-23 13:39:44 回复(0)

Python

questRush

class ArrayMex:
    def findArrayMex(self, A, n):
        i = 0
        items = A 
        for j in xrange(n):
            if n >= items[j] > 0:
                items[i] = items[j]
                i += 1
        for k in xrange(i):
            v = abs(items[k])
            items[v - 1] = - abs(items[v - 1])
        for w in xrange(i):
            if items[w] > 0:
                return w + 1
        return i + 1

编辑于 2017-04-02 18:47:10 回复(0)