Total Accepted: 87074 Total Submissions: 348588 Difficulty: Hard Contributors: Admin Given an unsorted integer array, find the first missing positive integer.
For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
方法： 遍歷一遍，把正確合法的正整數(shù)方在正確的位置上即可。比如我們找到元素5，就把5換到A[4]上，因?yàn)閿?shù)組從0下標(biāo)開始。最終結(jié)果數(shù)組A[i] != i+1 的就是該位置上的正整數(shù)沒有出現(xiàn)過，返回i+1即可。
代碼如下：
class Solution(object): def firstMissingPositive(self, nums): n = len(nums) for i in range(0, n): while nums[i] > 0 and nums[i] <= n and nums[nums[i]-1] != nums[i]: nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] for i in range(0, n): if nums[i] != i+1: return i+1 return n+1呵呵，人生苦短，我用Python。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
