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

背景

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

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

示例1

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

输出：2

示例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)