FilesExpand file tree

master

/

First_Missing_Positive.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

35 lines (32 loc) · 778 Bytes

master

/

First_Missing_Positive.py

Copy path

Top

File metadata and controls

• Code
• Blame

35 lines (32 loc) · 778 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

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

#

# Author : TangHanYi

# E-mail : thydeyx@163.com

# Create Date : 16-10-26 21:21:41

# File Name : First_Missing_Positive.py

# Desc :

"""

因为这个数不会超过N，所以把每个数交换到本来的位置上,扫描一边就好了

"""

class Solution(object):

def firstMissingPositive(self, nums):

n = len(nums)

if n == 0:

return 1

i = 0

while i < n:

if (nums[i] <= 0 or nums[i] > n) and i < n:

i += 1

continue

if nums[nums[i] - 1] != nums[i]:

nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

else:

i += 1

for i in range(n):

if nums[i] - 1 != i:

return i + 1

return n + 1

if __name__ == "__main__":

s = Solution()

nums = [3,4,-1,1]

print s.firstMissingPositive(nums)