全部标签
写点什么
MySQL云计算程序员行业资讯学习算法Python人工智能区块链Linux前端个人成长面试架构师编程企业动态新基建敏捷安全读书笔记高效工作团队管理创业活动专区生涯规划知识管理运维产品经理 查看更多

大厂面试算法题之数组

作者：程序员学长
  • 2021 年 12 月 10 日

  • 本文字数：29432 字

    阅读完需：约 97 分钟

数组

全文概览

数组的基础知识

数组的定义及特点

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

image-20211107160000971

数组主要有以下特点。

  1. 数组的下标是从 0 开始的。

  2. 连续的内存空间和相同的数据类型。

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

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

image-20211107161617888

解题有妙招

二分法

如果给定的数组是有序的，我们就需要考虑是否可以使用二分法来求解（二分法的时间复杂度是 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 插入到哈希表中。

image-20210927184217892

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 = 9print(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，直接返回。

image-20211004174113376

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

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 的窗口在序列上滑来滑去。

image-20210930111730950

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

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

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

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


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


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


  2. 下一个元素 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 = 3nums2 = [2,5,6]n = 3merge(nums1,m,nums2,n)print(nums1)
复制代码

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

image-20211001105533290

image-20211001105459602

image-20211001105558429

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

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 = 3nums2 = [2,5,6]n = 3merge(nums1,m,nums2,n)print(nums1)
复制代码

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

优化

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

image-20211001114449894

image-20211001114537857

我们来看一下代码实现。

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]

image-20211004104931296

分析问题

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

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

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

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 操作；依次类推，直到遍历完成。

image-20211004115702999

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]，会导致重复解，所以需要去掉。

image-20211107191548125

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

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。

image-20211013180122608

我们记数组的首个元素是 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] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

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

分析问题

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

image-20211019103253406

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

image-20211019103722071

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

算法

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

首先，我们用数组 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 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组的末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

image-20211019165600377

image-20211019165716505

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

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 小的数。

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

image-20211019214339618

image-20211019214457096

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，我们只需要返回两个数组首元素的最小值即可。

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

image-20211019224724752

image-20211019224810600

image-20211019224829400

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

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。

image-20211024123423464

image-20211024123443899

image-20211024123521634

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

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。

image-20211024130338002

image-20211024130423754

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

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)。

顺时针旋转数组

问题描述

LeetCode 面试题 01.07. 旋转矩阵

有一个 NxN 整数矩阵，请编写一个算法，将矩阵顺时针旋转 90 度。

要求：时间复杂度 O(N^2)，空间复杂度是 O(N^2)。

进阶：时间复杂度是 O(N^2)，空间复杂度是 O(1)

示例：

[                                                       [       [ 5, 1, 9,11],                旋转90度后                  [15,13, 2, 5],  [ 2, 4, 8,10],              ============>                [14, 3, 4, 1],  [13, 3, 6, 7],                                           [12, 6, 8, 9],   [15,14,12,16]                                            [16, 7,10,11]]                                                        ]
复制代码

分析问题

对于矩阵中的第一行元素来说，在经过 90 度旋转后，出现在了倒数第一列的位置上，如下图所示。

image-20211025162306911

并且，第一行的第 i 个元素在旋转后恰好是倒数第一列的第 i 个元素。对于第二行的元素也是如此，在旋转后变成倒数第二列的元素，并且第二行的第 i 个元素在旋转后恰好是倒数第二列的第 i 个元素。所以，我们可以得出规律，对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置，即对于矩阵中的 matrix[i] [j] 元素，在旋转后，它的新位置为 matrix [j] [n-i-1]。

所以，我们申请一个大小为 n * n 的新矩阵，来临时存储旋转后的结果。我们通过遍历 matrix 中的所有元素，根据上述规则将元素存放到新矩阵中的对应位置。在遍历完成后，再将新矩阵中复制到原矩阵即可。下面我们来看一下代码实现。

class Solution(object):    def rotate(self, matrix):        """        :type matrix: List[List[int]]        :rtype: None Do not return anything, modify matrix in-place instead.        """        #矩阵的大小        n = len(matrix)        #申请一个辅助矩阵        temp = [[0] * n for _ in range(n)]        #遍历矩阵中的所有元素，放到辅助矩阵的相应位置中        for i in range(n):            for j in range(n):                temp[j][n - i - 1] = matrix[i][j]                        #将辅助矩阵复制给矩阵        matrix[:] = temp
复制代码

该算法的时间复杂度是 O(N^2)，空间复杂度 O(N^2)。

进阶

那我们如何在不使用辅助空间的情况下，实现矩阵的原地旋转呢？我们来看一下方法一中为什么要引入辅助空间，对于 matrix 中的元素，我们使用公式**temp[j] [n - i - 1] = matrix[i] [j]**进行旋转，如果不申请辅助矩阵，我们直接把元素 matrix[i] [j]，放到矩阵 **matrix[j] [n - i - 1]位置，原矩阵中的 matrix[j] [n - i - 1]**元素就被覆盖了，这显然不是我们要的结果。

image-20211025183243579

image-20211025183304652

image-20211025183322988

当知道了如何原地旋转矩阵之后，这里还有一点需要明确：我们应该选取哪些位置进行上述的原地交换操作呢？通过上面的分析可以知道，一次可以原地交换四个位置，所以：

  1. 当 n 为偶数时，我们需要选取 n^2 / 4 = (n/2) * (n/2)个元素进行原地交换操作，可以将该图形分为四块，可以保证不重复、不遗漏旋转所有元素；

  2. 当 n 为奇数时，由于中心的位置经过旋转后位置不变，我们需要选取 (n^2-1)/4=(n-1)/2 * (n+1) /2 个元素进行原地交换操作，我们以 5*5 的矩阵为例，可以按照以下方式划分，进而保证不重复、不遗漏的旋转所有元素。

image-20211025183007908

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

class Solution(object):    def rotate(self, matrix):        #矩阵的大小        n = len(matrix)        for i in range(n // 2):            for j in range((n + 1) // 2):                #进行一轮原地旋转，旋转4个元素                temp = matrix[i][j]                matrix[i][j] = matrix[n - j - 1][i]                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]                matrix[j][n - i - 1] = temp
复制代码

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

##数组中的最长连续子序列

问题描述

LeetCode128. 最长连续序列

给定无序数组 arr，返回其中最长的连续子序列的长度(要求值连续，位置可以不连续，例如 3,4,5,6 为连续的自然数）。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：

输入：[100,4,200,1,3,2]

输出：4

说明：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

分析问题

因为给定的数组是无序的，所以我们最直观的想法就是遍历数组中的每个元素，然后考虑以其为起点，不断的在数组中寻找 x+1，x+2，...，x+n 是否存在，如果最长匹配到了 x+n，那么就表明以 x 为起点的最长连续序列为 x，x+1，x+2，...，x+n，其长度为 n+1。因为在数组中寻找一个数是否存在，是需要 O(n)的时间复杂度；而在哈希表中判断一个数是否存在只需要 O(1)的时间复杂度，所以我们可以通过引入一个哈希表，来减低该算法的时间复杂度。

在最坏的情况下，该算法的时间复杂度是 O(n^2)（即外层需要枚举 n 个数，内层也需要匹配 n 次），无法满足题目的要求，那我们如何来进行优化呢？

我们来分析一下算法的执行过程，如果我们已经知道了数组中存在有一个 x，x+1，x+2，...，x+n 的连续序列，那么我们就没有必要再继续以 x+1，x+2，....，x+n 为起点去数组中寻找连续序列了，因为得到的结果肯定不会优于以 x 为起点的连续序列。所以，我们在外层循环中如果碰到这种情况直接跳过就好。

具体做法是，我们在遍历的元素 x 时，去判读其前驱数 x-1 是否存在，如果存在的话，就不需要执行后面的逻辑，因为从 x-1 进行匹配的结果是优于从 x 进行匹配的，所以跳过 x。

image-20211102171231831

image-20211102171302801

image-20211102171331739

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

class Solution:    def longestConsecutive(self, nums):        #记录最长子序列的长度        length = 0
        #将数组中的元素放入set中        num_set = set(nums)
        for num in num_set:            #判断num-1是否存在于哈希表中，如果存在，直接跳过            if num - 1 not in num_set:                currentdata = num                currentlength = 1                #继续寻找                while currentdata + 1 in num_set:                    currentdata += 1                    currentlength += 1                #取最大值                length = max(currentlength, length)
        return length
复制代码

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

寻找峰值

问题描述

LeetCode 162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例：

输入：nums = [1,2,3,1]

输出：3 是峰值元素，你的函数应该返回其索引 2。

分析问题

峰值是指其值严格大于左右相邻值的元素，那么很显然数组中的最大值一定是一个峰值，因为它肯定大于它左右两侧的元素。所以，我们可以对数组进行一次遍历，然后求出其最大值的位置即可。该算法的时间复杂度是 O(n)，是不满足题目要求的。那我们如何进行优化呢。

我们可以这么来考虑，如果我们从一个位置开始，不断地向高处走，那么最终一定可以到达一个峰值位置。

因此，我们首先在 [0, n) 的范围内随机一个初始位置 i，随后根据 nums[i-1]，nums[i]，nums[i+1]三者的关系决定向哪个方向走。

  • 如何 nums[i-1] < nums[i] > nums[i+1]，那么位置 i 就是峰值的位置，我们直接返回 i。

  • 如果 nums[i-1] < nums [i] < nums[i+1] , 那么位置 i 处于上坡位置，要想找到峰值，需要往右走，即 i=i+1。

  • 如果 nums[i-1] > nums[i] > nums[i+1]，那么位置 i 处于下坡位置，要想找到峰值，需要往左走，季 i=i-1。

  • 如果 nums[i-1] > nums[i] < nums[i+1]，此时 i 处于坡底，要想找到峰值，两个方向都可以，我们假设这种情况需要往右边走。

综上所述，当 i 不是峰值时。

  • 如果 nums[i] > nums[i+1] , i 需要往左走，即执行 i=i-1。

  • 如果 nums[i] < nums[i+1]，i 需要往右走，即执行 i=i+1。

import randomclass Solution:    def findPeakElement(self, nums):        #数组的长度        n = len(nums)        #随机初始化一个位置        idx = random.randint(0, n - 1)
                #方便处理nums[-1] 以及 nums[n]的边界情况        def get_value(i):            if i == -1 or i == n:                return float('-inf')            return nums[i]        #当i不是峰值时，如果nums[i] < nums[i+1],此时需要向右走，即i=i+1        #否则需要向左走，即i=i-1        while not (get_value(idx - 1) < get_value(idx) > get_value(idx + 1)):            if get_value(idx) < get_value(idx + 1):                idx = idx + 1            else:                idx = idx - 1                        return idx
复制代码

在最坏的情况下，假设 nums 是单调递增的，并且我们是从 0 开始出发的，那这样就需要一直向右走到数组的最后一个位置，该算法的时间复杂度是 O(n)，而题目要求的时间复杂度是 O(logn)，显然是不符合的，那我们该如何求解呢？对于像 O(logn)这种形式的时间复杂度，我们最先想到的就是二分法，但是数组中的元素又不是排序的，那我们该如何使用二分法来求解此题呢？下面我们就来看一下。

通过分析，我们可以发现，当 nums[i] < nums[i+1]时，我们需要让 i 向右走，即执行 i=i+1，那么 i 和 i 左边的所有位置在后续的迭代中是永远不会走到的。因为假设此时在 i+1 的位置，要想向左走到位置 i，就需要 nums[i] > nums[i+1]，显然是不可能的。所以我们可以设计如下算法，首先创建两个变量 l、r 表示可走的左、右边界，开始时 l=0，r=n-1。

  1. 取区间[l，r]的中点，即 mid=(l+r)/2。

  2. 如果下标 mid 是峰值，直接返回。

  3. 如果 nums[mid] < nums[mid+1]，表示峰值在 mid 的右边，所以抛弃区间[l，mid]，在剩余的[mid+1，r]的区间内去寻找。

  4. 如果 nums[mid] > nums[mid+1]，表示峰值在 mid 的左边，所以抛弃区间[mid, r]，在剩余的[l，mid-1]的区间内去寻找。

这样的话，该算法每次淘汰掉一半的元素，所以时间复杂度是 O(logn)。

image-20211102230015514

image-20211102230038503

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

class Solution:    def findPeakElement(self, nums):        n = len(nums)        # 方便处理 nums[-1] 以及 nums[n] 的边界情况        def get_value(i):            if i == -1 or i == n:                return float('-inf')            return nums[i]
        #l,r代表区间的左右边界        l=0        r=n-1        ans=-1        while l <= r:            #取中点            mid = (l + r) // 2            #如果是峰值，直接返回            if get_value(mid - 1) < get_value(mid) > get_value(mid + 1):                ans = mid                break            #如果nums[mid]<nums[mid+1]，代表峰值在[mid+1,r]            #否则在区间[l,mid-1]            if get_value(mid) < get_value(mid + 1):                l = mid + 1            else:                r = mid - 1
        return ans

复制代码

二维数组中的查找

问题描述

LeetCode 剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例：

现有矩阵 matrix 如下：

[  [1, 2, 8, 9],  [2, 4, 9, 12],  [4, 7, 10, 13],  [6, 8, 11, 15]]
复制代码

给定 target = 9，返回 true。

给定 target = 20，返回 false。

分析问题

在二维数组中去查找一个元素，我们可以遍历一遍二维数组中的每一个元素，然后去判断是否和目标值相同。该算法的时间复杂度是 O(m*n)，它显然不是最优的解法。我们接下来来看一下如何进行优化。

因为给定的数组中的每一行、每一列都是递增排列的。当我们以左下角为起点时，只有向上和向右两种选择，上边的值严格的小，右边的值严格的大。所以，我们可以利用这个性质。

我们从二维数组的左下角为起点，开始遍历数组。

  • 当元素 matrix [i] [j] < target，说明 target 在 matrix [i] [j]的右方，所以向右走，即执行 j=j+1。

  • 当元素 matrix [i] [j] > target，说明 target 在 matrix [i] [j]的上方，所以向上走，即执行 i= i-1。

  • 当元素 matrix [i] [j] == target，代表已经找到了目标值，直接返回 true 即可。

最后，当超出二维数组的边界时，表示数组中不存在该元素，直接返回 false。

image-20211103115438892

image-20211103115457261

image-20211103115525124

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

class Solution(object):    def findNumberIn2DArray(self, matrix, target):        """        :type matrix: List[List[int]]        :type target: int        :rtype: bool        """        m=len(matrix)        #matrix为空时，直接返回False        if m==0:            return False        n=len(matrix[0])        #从左下角开始遍历        i = m - 1        j = 0        while i >= 0 and j <= n - 1:            # 相等返回True            if matrix[i][j] == target:                return True            # 大于向上走            elif matrix[i][j] > target:                i = i - 1            # 小于向右走            elif matrix[i][j] < target:                j = j + 1        return False
复制代码

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

数组中的逆序对

问题描述

LeetCode 剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数 P。

示例：

输入：[7,5,6,4]

输出：5

分析问题

这道题最容易想到的就是暴力解法，即使用两层 for 循环，去逐一判断是否构成逆序关系。

class Solution:    def reversePairs(self, nums) :        n = len(nums)        #如果数组中的元素的个数        # 为0或者1时，表示没有逆序对，直接返回0        if n < 2:            return 0        #逆序对的个数        res = 0        #两层循环去逐一判断是否是逆序对        for i in range(0,  n - 1):            for j in range(i + 1, n):                if nums[i] > nums[j]:                    res += 1        return res
复制代码

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

该算法显然不是最优解，我们第一次听说逆序对的这个概念，应该是在数组排序时。所以，我们这里可以采用归并排序算法来求解逆序对的个数。

首先，我们先来回顾一下什么是归并排序。归并排序是分治思想的典型应用，它包含以下三个步骤：

  1. 分解：假设待排序的区间为[l,r]，我们令 mid=(l+r)//2，将区间分成[l,mid]和[mid+1,r]两部分。

  2. 解决：使用归并排序递归的求解两个子序列，使其有序。

  3. 合并：把两个已经排好序的子序列[l,mid]和[mid+1,r]合并起来。

下面我们来看一下如何使用归并排序来求解逆序对？关键在于归并排序的合并步骤，即利用数组的部分有序性，一下子计算出一个数之前或者之后的逆序数的个数；下面我们来看一个具体的例子，假设目前有两个已经排好序的序列等待合并，分别是 L=[8，17，30，45] 和 R=[10，24，27，39]，如下图所示。

image-20211103165004253

我们来看一下如何把 L、R 合并成一个有序的数组。整体思路是将原数组拷贝到辅助数组，再使用双指针法，每次将较小的元素归并回去。

image-20211103172523805

image-20211103172556797

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

class Solution:    def reversePairs(self, nums) :         n = len(nums)         #数组中个数小于2时，不存在逆序对，所以返回0         if n < 2:            return 0
         #用于归并的辅助数组         temp = [0 for _ in range(n)]         return self.reverse_pairs(nums, 0, n - 1, temp)
    #归并排序nums    def reverse_pairs(self, nums, left, right, temp):        if left == right:            return 0        mid = (left + right)//2        #将nums分成左、右两部分，递归求解        left_pairs = self.reverse_pairs(nums, left, mid, temp)        right_pairs = self.reverse_pairs(nums, mid + 1, right, temp)
        #子序列[left, mid] 和 [mid + 1, right] 已经完成了排序并且计算好逆序对        reverse_pairs = left_pairs + right_pairs        #nums[mid] <= nums[mid + 1]，此时[left，right]已经是有序的了        #所以不存在横跨两个区间的逆序对，直接返回reverse_pairs即可        if nums[mid] <= nums[mid + 1]:            return reverse_pairs
        #计算跨两个区间的逆序对        cross_pairs = self.merge_and_count(nums, left, mid, right, temp)
        return reverse_pairs + cross_pairs
    def merge_and_count(self, nums, left, mid, right, temp):        """        [left, mid] 有序，[mid + 1, right] 有序，将两个有序的子序列合并成一个有序的子序列        """        #将nums的元素copy到辅助数组中        for i in range(left, right + 1):            temp[i] = nums[i]
        i = left        j = mid + 1        res = 0        for k in range(left, right + 1):            #i>mid,说明left部分已经遍历完，直接将right插入nums            if i > mid:                nums[k] = temp[j]                j += 1            #j>right,说明right部分已经遍历完，直接将left插入nums            elif j > right:                nums[k] = temp[i]                i += 1            # 此时left数组元素小，插入nums中，不计算逆序数            elif temp[i] <= temp[j]:                nums[k] = temp[i]                i += 1            # 此时right数组元素小，插入nums中，统计逆序对，            # 一次可以统计出一个区间的个数的逆序对            else:                nums[k] = temp[j]                j += 1                res += (mid - i + 1)        return res

复制代码

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

旋转数组

问题描述

LeetCode189. 旋转数组

一个数组 A 中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将 A 中的数据由（A0 A1……An-1 ）变换为（An-m…… An-1 A0 A1……An-m-1）（最后 M 个数循环移至最前面的 M 个位置)。

示例：

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

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

分析问题

这道题最直观的想法就是使用额外的数组来将每个元素放到正确的位置。我们用 n 来表示数组的长度，然后遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k) % n 的位置，最后将新数组拷贝到原数组即可。

class Solution:    def rotate(self,nums,k):        n=len(nums)        tmp=[0]*n
        for i in range(0,n):            #将数组nums[i]放到新数组的相应位置            tmp[(i+k)%n]=nums[i]        #将新数组拷贝到原数组        nums[:]=tmp[:]
复制代码

该算法的时间复杂度是 O(n)，空间复杂度也是 O(n)。但是题目要求不允许使用另外的数组，显然该算法是不符合题意的。我们来观察一下数组移动前后的变化，当我们将数组的元素向右移动 k 次后，尾部 k mod n 个元素会移动至数组的头部，其余元素向后移动 k mod n 个位置。因此我们可以采用数组翻转的方法来求解。具体思路如下：首先我们将所有元素进行翻转，这样尾部 k mod n 个元素就被移动到数组的头部。然后我们再翻转 [0, (k mod n)-1] 区间的元素和 [k mod n, n-1]区间的元素，即能得到最后的答案。

image-20211103213730385

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

class Solution:    #对数组中的元素进行翻转    def reverse(self,nums,start,end):        while start < end:            tmp=nums[start]            nums[start]=nums[end]            nums[end]=tmp            start=start+1            end=end-1    def rotate(self,nums,k):        n=len(nums)        k=k%n        #对数组进行反转        self.reverse(nums,0,n-1)        #对区间nums[0,k-1]再进行翻转        self.reverse(nums,0,k-1)        #对区间nums[k,n-1]再进行翻转        self.reverse(nums,k,n-1)
复制代码

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

调整数组顺序使奇数位于偶数前面

问题描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

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

输出：[1,3,2,4]

分析问题

这道题我们可以使用双指针法来求解，具体思路如下。

  1. 首先，申请两个指针 i 和 j，分别指向数组 nums 的左右两端，即 i=0，j=n-1。

  2. 当 i 所指的位置为奇数时，执行 i=i+1，直到遇到偶数。

  3. 当 j 所指的位置为偶数时，执行 j=j-1，直到遇到奇数。

  4. 然后交换 nums[i]和 nums[j]的值

  5. 重复上述操作，直到 i==j 为止。

image-20211104114617098

image-20211104114642721

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

class Solution(object):    def exchange(self, nums):        #申请两个变量i和j,开始时，指向数组的两端        i=0        j=len(nums)-1        while i < j:            #从i开始从左向右寻找，直到找到第一个偶数            while i < j and nums[i] % 2 == 1:                i = i + 1            #从j开始从右想左寻找，直到找到第一个奇数            while i < j and nums[j] % 2 == 0:                j = j - 1            nums[i], nums[j] = nums[j], nums[i]        return nums
复制代码

其实这道题我们还可以使用快慢指针法来求解，首先我们定义两个指针 fast 和 slow，fast 的作用是向前搜索奇数所在的位置，slow 的作用是指向下一个奇数应当存放的位置。在 fast 向前移动的过程中，当它搜索到奇数时，将它和 nums[slow]进行交换，然后让 slow 向前移动一个位置，重复上述操作，直到 fast 指向数组的末尾为止。

class Solution:    def exchange(self, nums):        slow = 0        fast = 0        #循环遍历，直到fast指向nums的末尾        while fast < len(nums):            #如果fast指向奇数，            #交换nums[slow]和nums[fast]            if nums[fast] % 2 == 1:                nums[slow], nums[fast] = nums[fast], nums[slow]                slow=slow+1            fast=fast+1        return nums
复制代码

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

矩阵乘法

问题描述

给定两个 n * n 的矩阵 A 和 B，求 A * B。

示例：

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

输出：[[7,6]，[13,14]]

分析问题

我们可以使用矩阵乘法规则来求解。对于 n * n 的矩阵 A 和矩阵 B 相乘，所得矩阵 C 的第 i 行第 j 列的元素可以表示为 Ci,j=Ai,1* B1,j + Ai,2 * B2,j + ... + Ai,n * Bn,j , 即等于 A 的第 i 行和 B 的第 j 列对应元素的乘积之和。

image-20211104150541839

class Solution:    def solve(self , a, b):        # write code here        #矩阵a和矩阵b是n*n的矩阵        n=len(a)        res=[[0] * n for _ in range(n)]
        for i in range(0,n):            for j in range(0,n):                for k in range(0,n):                    #C的第i行第j列的元素为                    #A的第i行和B的第j列对应元素乘积的和                    res[i][j] += a[i][k]*b[k][j]        return res
复制代码

该算法的时间复杂度是 O(N^3)，空间复杂度是 O(N^2)。

我们都知道对于二维数组来说，在计算机的内存中实际上是顺序存储的，如下所示：

image-20211104151742743

因为操作系统加载数据到缓存中时，都是把命中数据附近的一批数据一起加载到缓存中，因为操作系统认为如果一个内存位置被引用了，那么程序很可能在不久的未来引用附近的一个内存位置。所以我们通过调整数组的读取顺序来进行优化，使得矩阵 A 和 B 顺序读取，然后相继送入 CPU 中进行计算，最后使得运行时间能够更快。下面我们来看一下具体做法：

class Solution:    def solve(self , a, b):        # write code here        #矩阵a和矩阵b是n*n的矩阵        n=len(a)        res=[[0] * n for _ in range(n)]
        for i in range(0,n):            for j in range(0,n):                #顺序访问矩阵A的元素                temp=a[i][j]
                for k in range(0,n):                    #矩阵b的元素也是顺序访问的                    res[i][k] += temp * b[j][k]
        return res
复制代码

该算法的时间复杂度是 O(N^3)，但是该算法利用了缓存优化，顺序读取数组 A 和数组 B 中的元素，因此一般会比第一种方法运行更快。该算法的空间复杂度是 O(N^2)。

数字在升序数组中出现的次数

问题描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数。

示例：

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

输出：4

分析问题

不管数组是否有序，如果要查找数组中是否存在某个元素，我们只需要遍历一般数组就好。

class Solution:    def GetNumberOfK(self,data, k):        n=0        for x in data:            if x==k:               n=n+1        return n
复制代码

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

因为题目给定的数组是有序的，所以我们可以使用二分查找来求解。对于有序的数组，如果要寻找的目标值 target 有多个，那么他们肯定是连在一起的，所以我们可以通过二次二分查找，分别寻找目标值所在范围的上界和下界。首先，我们来看一下上界和下界的定义。

  • 下界定义为：如果存在目标值，则指向第一个目标值；如果不存在， 则指向大于目标值的第一个值。

  • 上界定义为：不管目标值存在与否，都指向大于目标值的第一个值。

image-20211104164129467

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

class Solution:    def GetNumberOfK(self,data, k):        l=0        r=len(data)-1
        #二分法寻找下界        while l<r:            mid = (r+l) // 2            if data[mid] < k:                l = mid + 1            else:                r = mid
        left=l        #寻找上界        l = 0        r = len(data)-1        while l<r:            mid=(r+l)//2            if data[mid] <= k:                l=mid+1            else:                r=mid
        right=l        return right - left
复制代码

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

三个数的最大乘积

问题描述

LeetCode628. 三个数的最大乘积

给定一个长度为 n 的无序数组 A ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

示例：

输入：nums = [1,2,3,4]

输出：24

分析问题

数组中三个数的最大乘积有以下二种情况。

  1. 如果数组中的元素全是非负数或者非正数，那么数组中最大的三个数相乘就是最大乘积。

  2. 如果数组中的元素既有正数也有负数，那么最大的乘积既可能是三个最大正数的乘积，也可能是两个最小负数（绝对值最大）和最大正数的乘积。

所以，我们只需要找出数组中最大的三个数以及最小的两个数，就可以求得结果。下面我们来看一下如何求解。最容易想到的方式就是先对数组进行降序排序，排好序的数组的前三位以及后两位就是要找的最大的三个数以及最小的两个数。

class Solution:    def maximumProduct(self,nums):        nums=sorted(nums)        n=len(nums)        return max(nums[0] * nums[1] * nums[n-1], nums[n - 3] * nums[n - 2] * nums[n-1])
复制代码

该算法的时间复杂度是 O(nlogn)，其中 n 为数组的长度。排序需要 O(nlogn)的时间。

空间复杂度是 O(logn)，主要是排序的开销。

其实我们也可以扫描一遍数组，就可以求出这五个数，如下所示。

import sysclass Solution:    def maximumProduct(self,nums):        #最小和第二小        min1=min2=sys.maxsize        #最大、第二大、第三大        max1=max2=max3=-sys.maxsize-1        for x in nums:            if x < min1:                min2=min1                min1=x            elif x<min2:                min2=x
            if x>max1:                max3=max2                max2=max1                max1=x            elif x>max2:                max3=max2                max2=x            elif x>max3:                max3=x
        return max(max1*max2*max3,max1*min1*min2)
复制代码

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

划线
评论
复制
发布于: 3 小时前阅读数: 6

版权声明: 本文为 InfoQ 作者【程序员学长】的原创文章。

原文链接:【http://xie.infoq.cn/article/4e87244ab15c2faefcb68e54b】。文章转载请联系作者。

数据结构算法大厂面试
用户头像

程序员学长

关注

程序员学长 2020.11.14 加入

公众号：程序员学长号主，专注分享算法、大数据、计算广告等技术

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
大厂面试算法题之数组