給定一個(gè)未排序的整數(shù)數(shù)組司致，找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)杀怠。
示例 1:
輸入: [1,2,0]
輸出: 3
示例 2:
輸入: [3,4,-1,1]
輸出: 2
示例 3:
輸入: [7,8,9,11,12]
輸出: 1
說(shuō)明:
你的算法的時(shí)間復(fù)雜度應(yīng)為O(n)管呵，并且只能使用常數(shù)級(jí)別的空間。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/first-missing-positive
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)茵汰，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
// 思路:
// 數(shù)據(jù)預(yù)處理：不考慮-1,0孽鸡，還有大于n的數(shù)经窖，因?yàn)槭状蝸G失的數(shù)一定小于或等于n+1
// 如果1不存在，則n=1
// 然后梭灿，遍歷画侣，若數(shù)字k出現(xiàn)，則將nums[k]的值替換為負(fù)數(shù)堡妒，nums[0]則用于保存n的值得正負(fù)
// 再次編譯配乱，出現(xiàn)第一個(gè)正式的小標(biāo)n就是最小的正整數(shù)，若遍歷完還沒(méi)有皮迟，判斷nums[0]搬泥，若還沒(méi)有則n=n+1
func firstMissingPositive(nums []int) int {
exist1 := false
n := len(nums)
for i := 0; i < n; i++ {
if nums[i] == 1 {
exist1 = true
}
if nums[i] <= 0 || nums[i] > n {
nums[i] = 1
}
}
if !exist1 {
return 1
}
if n == 1 {
return 2
}
for i := 0; i < n; i++ {
k := abs(nums[i])
if k == n {
// 重復(fù)數(shù)字不用算
if nums[0] > 0 {
nums[0] = -nums[0]
}
} else {
// 重復(fù)數(shù)字不用算
if nums[k] > 0 {
nums[k] = -nums[k]
}
}
}
// 遍歷，獲取第一個(gè)數(shù)==1即為n
for i := 1; i < n; i++ {
if nums[i] > 0 {
return i
}
}
if nums[0] > 0 {
return n
}
return n + 1
}
func abs(i int) int {
if i < 0 {
return 0 - i
}
return i
}
