字节跳动iOS面试算法题——当前数组中没有的最小正整数

背景

社畜初级程序员面试头条iOS开发，被完虐。其中一个算法题如下：

给定一个整数数组，输出当前数组中没有的最小正整数

示例1

输入：[0, -1, 1, -4, 5, 6, 10]

输出：1

示例2

输入：[1, 3, 5, 2,4]

输出：6

分析

暴力破解

首先想到的就是暴力遍历法，即从1开始在数组中比较搜索，直到在数组中没有找到。其代码实现如下：

// swift实现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次，所以其时间复杂度是O(N^2)，空间复杂度是O(1)

先排序，在搜索

因为给定的数组是未排序的，而我们需要找的是未出现最小的整数，所以可以先进行排序，而后在遍历这个数组找到未出现的最小整数。

其实现代码如下：

// swift实现func findMissMinUnsignedIntValue(_ nums: [Int]) -> Int {    let size = nums.count    var sortNums = nums;    sortNums.sort() // 先进行排序,排序的最快时间复杂度是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}

先排序后查找的算法时间复杂度是有排序和遍历决定的，即为O(NlogN) +O(N)，所以其时间复杂度为O(NlogN)，空间复杂度为O(1)**

使用缓存

这是一种空间换时间的方法，我们可以创立一个大小为N（N是原始数组的大小）数组进行来标记能否出现过该整数。其原理如下：

min_Int_01.png

实现代码如下：

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}

有代码可知，我们只遍历了一次原始数组，但是同时创立了一个大小为N的数组进行标记，所以其时间复杂度为O(N)，控件复杂度为O(N)

缓存思想，不使用额外的空间

前面我们使用了一个额外的数组进行标记，假如不使用额外的数组，应该如何进行标记呢？

那么我们只能在本身的数组上进行操作了，这里我们可以利用本身整数的特性，正数和负数来进行标记。基本步骤如下;

• 将原始数组小于等于0的数，都置为N+1。
• 遍历数组，将数组值对应位置的值标记成负数，注意在取值时，要取绝对值。
• 遍历数组，第一个不为负数的值的下标即是未出现的最小整数。

原理如下：

min_Int_02.png

代码如下：

func findMissMinUnsignedIntValue_cache2(_ nums: [Int]) -> Int {    let size = nums.count    if size == 0 {        return 1    }        var mutableNums = nums    // 1.将负数置为正数N+1    for index in 0..<size {        if mutableNums[index] <= 0 {            mutableNums[index] = size + 1        }    }        // 2. 将对应元素的值索引位置的值置为负数    for index in 0..<size {        let tmpNum = abs(mutableNums[index])        if tmpNum <= size {            mutableNums[tmpNum - 1] = -abs(mutableNums[tmpNum - 1])        }    }        // 3. 找到第一个>=0的位置索引    for index in 0..<size {        if mutableNums[index] > 0 {            return index + 1        }    }        return size + 1}

该算法是使用自身数组作为缓存解决，所以其时间复杂度为O(N)，空间复杂度为O(1)