背景
社畜初級(jí)程序員面試頭條iOS開發(fā)鲸鹦，被完虐。其中一個(gè)算法題如下：
給定一個(gè)整數(shù)數(shù)組覆积，輸出當(dāng)前數(shù)組中沒有的最小正整數(shù)
示例1
輸入：[0, -1, 1, -4, 5, 6, 10]
輸出：2
示例2
輸入：[1, 3, 5, 2,4]
輸出：6
分析
暴力破解
首先想到的就是暴力遍歷法庵朝，即從1開始在數(shù)組中比較搜索椎瘟，直到在數(shù)組中沒有找到。其代碼實(shí)現(xiàn)如下：
// swift實(shí)現(xiàn)
func findMissMinUnsignedIntValue(_ nums: [Int]) -> Int {
let size = nums.count
var i = 1
while i <= size {
var j = 0
for index in 0..<size {
if i == nums[index] {
break
}
j += 1
}
if j == size {
return i
}
i += 1
}
return i
}
暴力算法由于需要嵌套遍歷N次汰蜘，所以其時(shí)間復(fù)雜度是O(N^2)，空間復(fù)雜度是O(1)
先排序泼舱，在搜索
由于給定的數(shù)組是未排序的，而我們需要找的是未出現(xiàn)最小的整數(shù)危喉，所以可以先進(jìn)行排序，然后在遍歷這個(gè)數(shù)組找到未出現(xiàn)的最小整數(shù)氧急。
其實(shí)現(xiàn)代碼如下：
// swift實(shí)現(xiàn)
func findMissMinUnsignedIntValue(_ nums: [Int]) -> Int {
let size = nums.count
var sortNums = nums;
sortNums.sort() // 先進(jìn)行排序,排序的最快時(shí)間復(fù)雜度是O(N*logN)
var retValue = 1
for index in 0..<size {
if sortNums[index] <= 0 {
continue
} else {
if sortNums[index] != retValue {
return retValue
}
retValue += 1
}
}
return retValue
}
先排序后查找的算法時(shí)間復(fù)雜度是有排序和遍歷決定的钉寝，即為O(NlogN) +O(N)腥沽，所以其時(shí)間復(fù)雜度為O(NlogN)师溅，空間復(fù)雜度為O(1)**
使用緩存
這是一種空間換時(shí)間的方法矿筝，我們可以創(chuàng)建一個(gè)大小為N（N是原始數(shù)組的大小）數(shù)組進(jìn)行來標(biāo)記是否出現(xiàn)過該整數(shù)鼻疮。其原理如下：
實(shí)現(xiàn)代碼如下：
func findMissMinUnsignedIntValue(_ nums: [Int]) -> Int {
let size = nums.count
if size == 0 {
return 1
}
var flags: [Int] = Array(repeating: 0, count: size)
for index in 0..<size {
if nums[index] >= 0 && nums[index] < size {
flags[nums[index]] = 1
}
}
for index in 0..<flags.count {
if flags[index] == 0 {
return index
}
}
return size
}
有代碼可知琉闪，我們只遍歷了一次原始數(shù)組斯入，但是同時(shí)創(chuàng)建了一個(gè)大小為N的數(shù)組進(jìn)行標(biāo)記闹伪，所以其時(shí)間復(fù)雜度為O(N)，控件復(fù)雜度為O(N)
緩存思想，不使用額外的空間
前面我們使用了一個(gè)額外的數(shù)組進(jìn)行標(biāo)記，如果不使用額外的數(shù)組，應(yīng)該如何進(jìn)行標(biāo)記呢？
那么我們只能在本身的數(shù)組上進(jìn)行操作了，這里我們可以利用本身整數(shù)的特性，正數(shù)和負(fù)數(shù)來進(jìn)行標(biāo)記恼布。基本步驟如下;
- 將原始數(shù)組小于等于0的數(shù)奸忽，都置為N+1富俄。
- 遍歷數(shù)組悠瞬，將數(shù)組值對應(yīng)位置的值標(biāo)記成負(fù)數(shù)，注意在取值時(shí)晾捏，要取絕對值。
- 遍歷數(shù)組，第一個(gè)不為負(fù)數(shù)的值的下標(biāo)即是未出現(xiàn)的最小整數(shù)。
原理如下：
代碼如下：
func findMissMinUnsignedIntValue_cache2(_ nums: [Int]) -> Int {
let size = nums.count
if size == 0 {
return 1
}
var mutableNums = nums
// 1.將負(fù)數(shù)置為正數(shù)N+1
for index in 0..<size {
if mutableNums[index] <= 0 {
mutableNums[index] = size + 1
}
}
// 2. 將對應(yīng)元素的值索引位置的值置為負(fù)數(shù)
for index in 0..<size {
let tmpNum = abs(mutableNums[index])
if tmpNum <= size {
mutableNums[tmpNum - 1] = -abs(mutableNums[tmpNum - 1])
}
}
// 3. 找到第一個(gè)>=0的位置索引
for index in 0..<size {
if mutableNums[index] > 0 {
return index + 1
}
}
return size + 1
}
該算法是使用自身數(shù)組作為緩存處理帮寻，所以其時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)
