数组

全文概览

##数组的基础知识

数组的定义及特点

数组是一种线性表数据结构，是在连续内存空间上的存储相同类型数据的集合。

数组主要有以下特点。

1. 数组的下标是从0开始的。
2. 连续的内存空间和相同的数据类型。

正是因为数组的内存空间是连续的，所以我们可以“随机访问”数组内的元素。但有利有弊，如果想要在数组中插入或者删除一个元素，为了保证数组的内存空间的连续，就难免要移动其他元素。

例如要删除下标为2的元素，需要对下标2后面的元素都需要向前移动。如图所示：

解题有妙招

二分法

如果给定的数组是有序的，我们就需要考虑是否可以使用二分法来求解（二分法的时间复杂度是O(logn)）。面试中二分法是面试中常考的知识点，建议大家一定要多锻炼手撕二分的能力。

双指针法

我们可以通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。例如，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(N^2)减低到O(N)。

滑动窗口

顾名思义，所谓的滑动窗口就是可以在一个序列上进行滑动的窗口。其中窗口大小有固定长度的，也有可变长度的。例如给定数组[2,2,3,4,8,99,3]，窗口大小为3，求出每个窗口的元素和就是固定大小窗口的问题，如果求数组[2,2,3,4,8,99,3]的最长连续子数组就是窗口可变的问题。使用滑动窗口，我们可以减低算法是时间复杂度。

使用滑动窗口求解问题时，主要需要了解什么条件下移动窗口的起始位置，以及何时动态的扩展窗口，从而解决问题。

哈希表法

如果需要在数组中查找某个元素是否存在时，我们可以使用哈希表法，可以将查找元素的时间复杂度从O(n)减低到O(1)。

##两数之和

问题描述

LeetCode 1. 两数之和

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

分析问题

拿到这个问题，最简单直观的想法就是对于数组中的每个元素x，去寻找数组中是否存在target-x。

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        #对于数组中的每个元素i
        #位于它之前的元素都已经和它匹配过了，不需要重复进行匹配
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

我们可以很清楚的知道，这个算法的时间复杂度是O(n^2)。那我们该如何降低时间复杂度呢？可以注意到该算法复杂度高的原因在于寻找元素target-x的时候，需要遍历一遍数组，所以我们需要对这一块进行优化。我们可以采用哈希表，将寻找元素target-x的时间复杂度由O(n)降低到O(1)。

我们在遍历数组时，对于每个元素x，我们首先查询哈希表中是否存在target-x，如果存在，将匹配到的结果直接返回，如果不存在，我们把x插入到哈希表中。

Tips: 我们这里使用字典来代替哈希表，当插入的元素重复时，我们覆盖就好了，这样可以保证查找的时间复杂度为O(1)。为什么这里可以覆盖呢，因为题目要求是找两个数和等于target，当有两个元素重复时，我们认为它们是等价的，所以我们只需要保留一个就好了。

def twoSum(nums, target):
    hash_table = dict()
    for i, num in enumerate(nums):
        if hash_table.__contains__(target-num):
            return [hash_table[target - num], i]
        hash_table[nums[i]] = i
    return []

nums = [2,7,11,15]
target = 9
print(twoSum(nums,target))

我们可以看到该算法的时间复杂度是O(n)，空间复杂度也是O(n)。

优化

**当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(N^2)减低到O(N)。 **所以我们可以采用双指针法来求解。首先，我们先对数组进行排序，然后用left和right指针分别指向数组的左边和右边，此时sum=nums[left]+nums[right]，根据sum和target的大小关系，我们来移动指针。

1. 如果sum>target，右指针左移，减小sum的值，即right=right-1。
2. 如果sum<target，左指针右移，增大sum的值，即left=left+1。
3. 如果sum=target，直接返回。

下面我们来看一下代码的实现。

def twoSum(nums, target):
    nums=sorted(nums)
    left=0
    right=len(nums)-1
    while left < right:
        sum=nums[left]+nums[right]
        if sum>target:
            right=right-1
        elif sum<target:
            left=left+1
        else:
            return [left,right]

利用sorted进行排序，时间复杂度是O(nlogn)，空间复杂度是O(n)。所以该算法的时间复杂度是O(nlogn)，空间复杂度是O(n)。

最长无重复子数组

问题描述

LeetCode3. 无重复字符的最长子串

给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。

示例

输入：[2,2,3,4,8,99,3]

返回值：5

说明：[2,3,4,8,99]是最长子数组

分析问题

在开始之前，我们首先介绍一下什么是滑动窗口。顾名思义，所谓的滑动窗口就是可以在一个序列上进行滑动的窗口。如图所示，假设，我们的序列为abcabcbb，我们这里定义了一个固定大小为3的窗口在序列上滑来滑去。

在实际的使用中，我们使用的滑动窗口都是可变长度的。

我们可以使用双指针来维护窗口的开始和结束，通过移动左、右指针来实现窗口大小的改变和窗口的滑动。

我们来看一下题目，题目是求最长无重复元素子数组，如果我们可以求出所有的无重复元素的子数组，那取出最长的不就好了。下面我们来看一下如何求解。我们只需要维护一个在数组中进行滑动的窗口就好。

1. 开始时2不在窗口中，所以扩大窗口。

2. 下一个元素2在窗口中出现，所以我们要将出现过的元素及其左边的元素统统移出窗口，即2。

3. 接下来的元素3、4、8、99都没在窗口中出现过，所以我们把它们都加入到窗口中。

4. 下一个元素3在窗口出现过，所以我们要移除出现过的元素及其左边的元素，即2，3。

下面我们来看一下代码如何实现。

    if not s:
        return 0
    left = 0
    # 记录每个字符是否出现过
    window = set()
    n = len(s)
    max_len = 0
    for i in range(n):
        #如果出现过，移除重复元素及其左边的元素
        while s[i] in window:
            window.remove(s[left])
            left += 1
        #没出现过，加入window
        window.add(s[i])

        max_len = max(len(window),max_len)
        
    return max_len

该算法的时间复杂度是O(n)。

合并两个有序数组

问题描述

LeetCode 88. 合并两个有序数组

给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例：

输入：nums1 = [1,2,3,0,0,0]， m = 3，nums2 = [2,5,6]，n = 3

输出：[1,2,2,3,5,6]

解释：需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] 。

###分析问题

最简单暴力的方法就是直接把nums2放入nums1的后n个位置，然后直接对nums1进行排序就好了。我们这里就不在赘述。

def merge(nums1, m, nums2, n):
    nums1[m:] = nums2
    nums1.sort()

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1,m,nums2,n)
print(nums1)

那么既然给定的两个数组是有序的，那我们何不把这个条件利用起来，来优化代码。所以，我们可以使用两个指针p1和p2分别指向两个数组的起始位置，然后比较大小，将较小的放入结果中，然后指针后移，直到将所有元素都排好序。

下面我们来看一下代码的实现。

def merge(nums1, m, nums2, n):
    #暂时存放排好序的元素
    sorted = []
    p1, p2 = 0, 0
    #没有遍历完数组时
    while p1 < m and p2 < n:
        #p1元素遍历完
        if nums1[p1] <= nums2[p2]:
            sorted.append(nums1[p1])
            p1 += 1
        else:
            sorted.append(nums2[p2])
            p2 += 1
    if p1 == m:
        for x in nums2[p2:]:
            sorted.append(x)
    else:
        for x in nums1[p1:m]:
            sorted.append(x)
    nums1[:] = sorted

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1,m,nums2,n)
print(nums1)

我们可以知道这里的时间复杂度是O(m+n)，空间复杂度也是O(m+n)。

优化

在使用双指针法时，我们从前往后遍历数组，如果直接使用nums1存储合并结果的话，nums1 中的元素可能会在取出之前被覆盖。所以我们引入了一个临时变量sorted来存储。那有什么办法可以避免nums1中的元素被覆盖呢？既然从前往后不可以，那么我们能从后往前吗？因为nums1的后半部分是空的，可以直接覆盖而不会影响结果，所以这里引入了逆向双指针法。

我们来看一下代码实现。

def merge(nums1, m, nums2, n):
    #指向数组的末尾元素
    p1 = m -1
    p2 = n - 1
    tail = m + n - 1
    while p1 >= 0 or p2 >= 0:
        #表示nums1遍历完成
        if p1 == -1:
            nums1[tail] = nums2[p2]
            p2 -= 1
        #表示nums2遍历完成
        elif p2 == -1:
            nums1[tail] = nums1[p1]
            p1 -= 1
        #将大的元素合并
        elif nums1[p1] >= nums2[p2]:
            nums1[tail] = nums1[p1]
            p1 -= 1
        else:
            nums1[tail] = nums2[p2]
            p2 -= 1
        tail -= 1

该算法的时间复杂度是O(m+n)，空间复杂度是O(1)。

螺旋矩阵

问题描述

LeetCode 54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]

输出：[1,2,3,6,9,8,7,4,5]

分析问题

题目要求是按照顺时针螺旋顺序输出，即先从左到右、然后从上到下、再从右到左、最后从下到上，依次类推，直到全部元素遍历完为止。在遍历的过程中，最关键的一点就是要记录哪些元素已经被访问过了，如果遇到被访问过的元素，我们就需要顺时针的调整一下方向。

判断元素是否被访问过，最直观的想法就是声明一个和矩阵大小相同的矩阵，来标识矩阵中的元素是否被访问过。

我们来看一下代码如何实现。

def spiralOrder(matrix):
    #矩阵为空，直接返回
    if not matrix or not matrix[0]:
        return []
    rows=len(matrix)
    columns=len(matrix[0])
    visited = [[False for _ in range(columns)] for _ in range(rows)]
    #总元素的个数
    count=rows*columns
    result=[0]*count
    #代表方向，即从左到右、从上到下、从右到左、从下到上
    directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    row, column = 0, 0
    #从左上角开始遍历
    directionIndex = 0
    for i in range(count):
        result[i] = matrix[row][column]
        #将访问过的元素进行标记
        visited[row][column] = True
        nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
        #不越界，并且已经被访问过了，顺时针调整方向
        if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):
            directionIndex = (directionIndex + 1) % 4

        row += directions[directionIndex][0]
        column += directions[directionIndex][1]
    return result

由于创建了一个和原始矩阵一样大小的矩阵来表示元素是否被访问过，所以该算法的空间复杂度是O(mn)。矩阵中的元素都会被遍历一次，所以该算法的时间复杂度也是O(mn)。

优化

那有什么方法可以优化算法的空间复杂度吗？即我们不用开辟新的空间来保存矩阵中的元素是否被访问过。

其实我们可以在遍历的过程中不断的改变边界条件，当矩阵的第一行元素被访问过之后，那上边界就需要进行+1操作；如果最后一列元素被访问过了，那么右边界需要进行-1操作；如果最后一行元素被访问过了，那下边界需要进行-1操作；如果第一列被访问过了，那需要进行+1操作；依次类推，直到遍历完成。

def spiralOrder(matrix):
    # 矩阵为空，直接返回
    if not matrix or not matrix[0]:
        return []
    rows = len(matrix)
    columns = len(matrix[0])
    result=[]
    #开始时，左、右、上、下边界
    left=0
    right=columns-1
    up=0
    down=rows-1
    while True:
        #从左到右
        for i in range(left,right+1):
            result.append(matrix[up][i])
        #上边界调整
        up=up+1
        #越界，退出
        if up>down:
            break
        #从上到下
        for i in range(up,down+1):
            result.append(matrix[i][right])
        #右边界调整
        right=right-1
        # 越界，退出
        if right<left:
            break
        #从右到左
        for i in range(right,left-1,-1):
            result.append(matrix[down][i])
        #下边界调整
        down=down-1
        if down<up:
            break
        #从下到上
        for i in range(down,up-1,-1):
            result.append(matrix[i][left])
        left=left+1
        if left>right:
            break
    return result

该算法的时间复杂度是O(m*n)，空间复杂度是O(1)。

数组中和为 0 的三个数

问题描述

LeetCode 剑指 Offer II 007. 数组中和为 0 的三个数

给定一个包含n个整数的数组nums，判断nums中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且不重复的三元组。

示例：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

分析问题

这道题目算是二数之和的升级版，所以我们也可以采用双指针法来求解。那三个数如何采用双指针法呢，其实很简单，我们先把一个数固定下来，然后另外两个数再使用双指针去寻找不就好了。按照惯例，我们首先对数组进行排序，然后固定第一个数first，假设为nums[i]，然后再使用双指针法在数组中寻找两数之和等于-nums[i]即可。由于题目要求所求的三元组是不重复的，所以需要判断去掉重复解。重复解主要有以下两种情况。

1. 当nums[first]=nums[first-1]，由于我们已经把第一个元素是**nums[first-1]**的三元组已经求解过了，所以没必要重复求解。
2. 当nums[first]+nums[left]+nums[right]=0时，如果nums[left]=nums[left+1]或者nums[right]=nums[right+1]，会导致重复解，所以需要去掉。

我们来看一下代码的实现。

def threeSum(nums):
    n=len(nums)
    result=[]
    if n<3:
        return result
    nums=sorted(nums)
    print(nums)
    #遍历数组
    for i in range(n):
        #固定第一个数
        first=nums[i]
        #第一个数大于0，由于第二个、第三个数都大于第一个数
        #所以不可能相加等于0
        if first>0:
            break
        #已经查找过了，所以不需要再继续寻找，直接跳过
        if i>0 and first==nums[i-1]:
            continue
        #第三个数，开始时指向最数组的最右端
        target=-first
        right=n-1
        left=i+1
        while left<right:
            if nums[left]+nums[right]==target:
                result.append([nums[i],nums[left],nums[right]])
                #如果left和left+1对于的元素相同，由于left已经添加到result中了
                #为了避免重复，我们跳过相同的元素
                while left<right and nums[left]==nums[left+1]:
                        left=left+1
                #同理，跳过和right相同的元素
                while left<right and nums[right]==nums[right-1]:
                        right=right-1
                left=left+1
                right=right-1

            elif nums[left]+nums[right]>target:
                right=right-1
            else:
                left=left+1
    return result

nums=[-1,0,1,2,-1,-4]
print(threeSum(nums))

数组中出现次数超过一半的数字

问题描述

LeetCode 剑指 Offer 39. 数组中出现次数超过一半的数字

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

示例：

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

输出：2

分析问题

哈希表法

我们最容易想到的方法就是使用哈希表法，去统计每个数字出现的次数，即可很容易的求出众数。

def majorityElement(nums):
    #用字典来保存每个数字出现的次数
    data_count = {}
    for x in nums:
        if x in data_count:
            data_count[x] = data_count[x] + 1
        else:
            data_count[x] = 1
    max_value=0
    max_key=0
    #遍历字典，取出次数最大的
    #因为题目说给定的数组一定存在众数
    #所以最大的次数就是众数
    for key in data_count:
        value=data_count[key]
        if value>max_value:
            max_value=value
            max_key=key
    return max_key

data=[1,2,3,2,2,2,5,4,2]
print(majorityElement(data))

该算法的时间复杂度是O(n)，空间复杂度也是O(n)。

排序算法

我们将数组进行排序，那排序后的数组的中点一定就是众数。

def majorityElement(nums):
        #将数组排序
        nums.sort()
        #返回排序数组中的中点
        return nums[len(nums) // 2]

data=[1,2,3,2,2,2,5,4,2]
print(majorityElement(data))

Boyer-Moore 投票算法

这道题最经典的解法是Boyer-Moore 投票算法。Boyer-Moore 投票算法的核心思想是票数正负抵消，即遇到众数时，我们把票数+1，遇到非众数时，我们把票数-1，则所有的票数和一定是大于0的。

我们假设数组nums的众数是x，数组的长度为n。我们可以很容易的知道，若数组的前a个数字的票数和为0，那么剩余n-a个数字的票数和一定是大于0的，即后n-a个数字的众数仍然为x。

我们记数组的首个元素是n1，数组的众数是x，遍历并统计票数。当发生票数和为0时，数组剩余元素的众数一定也是x，这是因为：

1. 当n1等于x时，抵消的所有数字中，有一半是众数x。
2. 当n1不等于x时，抵消的所有数字中，众数的个人最少为0，最多为一半。

所以，我们在去掉m个字符里，最多只去掉了一半的众数，所以在剩余的n-m个元素中，x仍然为众数。利用这个特性，在每次遇到票数和为0时，我们都可以缩小剩余数组区间。当遍历完成时，最后一轮假设的数字即为众数。

class Solution:
    def majorityElement(self, nums):
        #票数和
        counts=0
        for num in nums:
            #如果票数和为0，我们假设num元素为众数
            if counts == 0:
                x = num
            #如果是众数票数+1，否则票数-1
            if num==x:
                counts=counts+1
            else:
                counts=counts-1
        return x

该算法的时间复杂度是O(n)，空间复杂度是O(1)。

合并区间

问题描述

LeetCode 56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

输入：intervals = [ [1，3]，[2，6]，[8，10]，[15，18] ]
输出：[ [1，6]，[8，10]，[15，18] ]
解释：区间 [1，3] 和 [2，6] 重叠，将它们合并为 [1，6]

分析问题

对于任意两个区间A和B，它们之间的关系可以有以下6种情况。

我们将这两个区间进行比较、交换，使得第一个区间的起始位置 ≤ 第二个区间的起始位置这个条件成立，这样的话，我们就可以把这6种情况转换成以下3种。

按照这个思路，我们将所有区间按照左端点进行排序，那么就可以保证任意连续的两个区间，第一个区间的起始位置 ≤ 第二个区间的起始位置，所以他们的关系只有上面三种情况。

算法

对于上面的三种情况，我们可以采用如下算法来求解。

首先，我们用数组 merged 存储最终的答案。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

• 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，即上图中的第二种情况，那么它们不会重合。我们可以直接将这个区间加入数组 merged 的末尾；

• 否则，它们是有重合部分的，即上图中的第一、三种情况，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

这样，我们就可以解决上述的三种情况，下面我们来看一下代码的实现。

class Solution:
    def merge(self, intervals):
        #将区间数组按照左端点进行升序排序
        intervals.sort(key=lambda x: x[0])
        #存放合并后的结果
        merged = []
        for interval in intervals:
            #如果列表为空
            #或者当前区间的左端点大于merged最后一个元素的右端点，直接添加
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                #否则的话，我们就可以与上一区间进行合并
                #修改merged最后一个元素的右端点为两者的最大值
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

该算法的时间复杂度是O(nlogn)，其中n是区间的数量，除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O*(*n logn)。空间复杂度是O(logn)。

在两个长度相等的排序数组中找到上中位数

问题描述

LeetCode 4. 寻找两个正序数组的中位数

给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。上中位数：假设递增序列长度为n，为第n/2个数。

要求：时间复杂度 O (n)，空间复杂度 O(1)。

进阶：时间复杂度为O(logN)，空间复杂度为O(1)。

示例：

输入：[1，2，3，4]，[3，4，5，6]

返回值：3

说明：总共有8个数，上中位数是第4小的数，所以返回3。

分析问题

这道题最直观的想法就是，使用归并排序的方式，将两个有序数组合并成一个大的有序数组。大的有序数组的上中位数为第n/2个数。我们可以知道该算法的时间复杂度是O(N)，空间复杂度也是O(N)，显然不符合题目要求的O(1)的空间复杂度。其实，我们也不需要合并两个有序数组，我们只需要找到上中位数的位置即可。对于给定两个长度为N的数组，我们可以知道其中位数的位置为N，所以我们维护两个指针，初始时分别指向两个数组的下标0的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组的末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

下面我们来看一下代码如何实现。

class Solution:
    def findMedianinTwoSortedAray(self , arr1 , arr2 ):
        # write code here
        #数组的长度
        N=len(arr1)
        #定义两个指针，指针两个数组的开始位置
        p1=p2=0
        ans=0
        while p1+p2<N:
            #移动较小元素的指针位置
            if arr1[p1]<=arr2[p2]:
                ans=arr1[p1]
                p1=p1+1
            else:
                ans=arr2[p2]
                p2=p2+1

        return ans

该算法的时间复杂度是O(n)，空间复杂度是O(1)。

进阶

下面我们来看一下如何把时间复杂度降低为O(logN)。我们这里可以采用二分查找的思想来求解。

对于长度为N的数组arr1和arr2来说，它的上中位数是两个有序数组的第N个元素。所以，我们把这道题目可以转换成寻找两个有序数组的第k小的元素，其中k=N。

要找到第N个元素，我们可以比较arr1[N/2-1]和arr2[N/2-1]，其中“/”代表整数除法。由于arr1[N/2-1]和arr2[N/2-1]的前面分别有arr1[0…N/2-2]和arr2[0…N/2-2]，即N/2-1个元素。对于arr1[N/2-1]和arr2[N/2-1]的较小值，最多只会有N/2-1+N/2-1=N-2个元素比它小，所以它不是第N小的元素。

因此，我们可以归纳出以下三种情况。

• 如果arr1[N/2-1] < arr2[N/2-1]，则比arr1[N/2-1] 小的数最多只有 arr1的前N/2-1个数和arr2的前N/2-1个数，即比arr1[N/2-1] 小的数最多只有N-2个，因此arr1[N/2-1]不可能是第N个数，arr1[0]到arr1[N/2-1]也都不可能是第N个数，所以可以删除。
• 如果arr1[N/2-1] > arr2[N/2-1]，则可以排除arr2[0]到arr2[N/2-1]。
• 如果arr1[N/2-1]==arr2[N/2-1]，可以归为第一种情况进行处理。

可以看到，经过一轮比较后，我们可以排查N/2个不可能是第N小的数，查找范围缩小了一半。同时，我们将在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减少 N 的值，这是因为我们排除的数都不大于第 N 小的数。

下面我们来看一个具体的例子。

class Solution:
    def findMedianSortedArrays(self, arr1, arr2):
        N = len(arr1)
        #如果N=1,直接返回两个数组的首元素的最小值即可
        if N==1:
            return min(arr1[0],arr2[0])

        index1, index2 = 0, 0
        #中位数位置为N,不过超过分区数组的下标
        k=N
        while k>1:
        
            new_index1 = index1 +  k // 2 - 1
            new_index2 = index2 +  k // 2 - 1
            data1, data2 = arr1[new_index1], arr2[new_index2]
            #选择较小值，同时将前k//2个元素删除
            if data1 <= data2:
                k=k-k//2
                #删除前k//2个元素
                index1 = new_index1+1
            else:

                k=k-k//2
                #删除前k//2个元素
                index2 = new_index2 + 1

        return min(arr1[index1],arr2[index2])

加餐

如果给定的两个有序数组大小不同，即给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

根据中位数的定义，当m+n为奇数时，中位数是两个有序数组的第(m+n+1)/2个元素。当m+n为偶数时，中位数是两个有序数组的第(m+n)/2和(m+n)/2+1个元素的平均值。因此这道题我们可以转化成寻求两个有序数组的第k小的数，其中k为(m+n)/2或者(m+n)/2+1。

所以该题的解题思路和上一题的解法类似，不过这里有一些情况需要特殊处理。

• 如果nums1[k/2-1]或者nums[k/2-1]越界，那么我们需要选择对应数组的最后一个元素，即min(k/2-1,m-1)或者min(k/2-1,n-1)。
• 如果一个数组为空，我们可以直接返回另一个数组中第 k 小的元素。
• 如果k=1，我们只需要返回两个数组首元素的最小值即可。

下面我们来看一下代码的实现。

下面我们来看一下代码的实现。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        #获取第k小的元素
        def getKthElement(k):
            #表示两个有序数组的下标位置
            index1, index2 = 0, 0
            while True:
                #如果一个数组遍历完成，则直接返回另一个数组的第k小元素
                if index1 == m:
                    return nums2[index2 + k - 1]
                if index2 == n:
                    return nums1[index1 + k - 1]
                #如果k为1，返回两个有序数组首元素的最小值
                if k == 1:
                    return min(nums1[index1], nums2[index2])

                #防止数组越界，所以取index1 + k // 2 - 1和m - 1的最小值
                new_index1 = min(index1 + k // 2 - 1, m - 1)
                #同理，取index2 + k // 2 - 1和 n - 1的最小值
                new_index2 = min(index2 + k // 2 - 1, n - 1)
                data1, data2 = nums1[new_index1], nums2[new_index2]
                #如果data1<data2
                if data1 <= data2:
                    #使k的值减少new_index1 - index1 + 1多个元素
                    k -= new_index1 - index1 + 1
                    #移除元素
                    index1 = new_index1 + 1
                else:
                    #使k的值减少new_index2 - index2 + 1多个元素
                    k -= new_index2 - index2 + 1
                    #移除元素
                    index2 = new_index2 + 1

        m, n = len(nums1), len(nums2)
        #两个数组的长度
        lens = m + n
        #如果为奇数，则中位数是第(lens+1)/2
        #如果为偶数，则中位数是lens/2和lens/2+1的平均值
        if lens % 2 == 1:
            return getKthElement((lens + 1) // 2)
        else:
            return (getKthElement(lens // 2) + getKthElement(lens // 2 + 1)) / 2.0

该算法的时间复杂度是O(log(m+n))，空间复杂度是O(1)。

缺失的第一个正整数

问题描述

LeetCode 41. 缺失的第一个正数

给你一个无重复元素未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。

示例：

输入：nums = [1，2，0]

输出：3

分析问题

对于一个无重复元素、长度为N的数组，其中没有出现的最小整数只能在[1,N+1]中，这是因为如果[1,N]在数组中都出现了，说明这N个数已经把数组填满了，那么答案是N+1，否则就是[1，N]中没有出现的最小整数。所以，我们可以申请一个辅助数组temp，大小为N，我们通过遍历原数组，将属于[1,N]范围内的数，放入辅助数组中相应的位置，使得temp[i-1] = i 成立。在遍历完成后，temp中第一个不满足temp[i-1] = i 条件的就是最小的正整数，如果都满足，那么最小正整数就是N+1。

下面我们来看一下代码实现。

class Solution:
    def firstMissingPositive(self, nums):
        n = len(nums)
        #申请一个临时数组，存放数组中的元素
        temp = [0]*n
        for i in range(n):
            #如果整数不在[1,N]的范围内，不做处理
            if nums[i] <= 0 or nums[i] > n:
                continue
            else:
                #否则把整数放入temp的相应位置
                temp[nums[i]-1]=nums[i]

        #遍历temp,找到第一个不满足temp[i]!=i+1的整数
        #就是代表数组中不存在的最小整数
        for i in range(n):
            if temp[i]!=i+1:
                return i+1
        #如果都存在，返回N+1
        return n+1

我们可以知道该算法的时间复杂度和空间复杂度都是O(n)，显然空间复杂度不满足题目要求，那我们该如何降低算法的空间复杂度呢？通过观察，我们可以发现辅助数组和原数组大小一样，那么我们能否复用原数组nums呢？答案显然是可以的。我们在遍历数组的过程中，假设遍历到的元素值为x，如果x属于[1,N]，我们将元素x和nums[x-1]的元素进行互换，使得x出现在正确的位置上，否则不做处理。当遍历完成后，nums中第一个不满足nums[i-1] = i 条件的就是最小的正整数，如果都满足，那么最小正整数就是N+1。

下面我们来看一下代码的实现。

class Solution:
    def firstMissingPositive(self, nums):
        #数组的长度
        n = len(nums)
        #遍历数组，将元素放到正确的位置
        for i in range(n):
            #如果nums[i]在[1,n]的范围内，并且nums[i]不在正确的位置上，我们进行互换
            #否则不做处理
            while 1 <= nums[i] <= n \
                    and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
                
        #找到数组中第一个不满足nums[i] != i + 1条件的
        #就是数组中的最小正整数
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        #如果都满足，最小的整数就是n+1    
        return n + 1

该算法的时间复杂度是O(n)，空间复杂度是O(1)。

由于篇幅长度限制，只能放这么多了，全文在以下链接中

大厂面试算法题详解