关于leetcode:面试高频算法题之数组系列

大家好，我是程序员学长~

明天给大家带来一篇面试高频算法题之数组的具体解析，全文蕴含19道大厂口试面试算法真题，一举拿下数组这个知识点，让算法不在成为进入大厂的绊脚石。

如果喜爱，记得点个关注哟~

本文有点长，我已将本文制作成带目录的PDF版本，获取本文PDF版本，请关注【程序员学长】，私信我。

github地址曾经更新，欢送star。
https://github.com/meetalgo/m...

全文概览

数组的基础知识

数组的定义及特点

数组是一种线性表数据结构，是在间断内存空间上的存储雷同类型数据的汇合。

数组次要有以下特点。

数组的下标是从0开始的。
间断的内存空间和雷同的数据类型。

正是因为数组的内存空间是间断的，所以咱们能够“随机拜访”数组内的元素。但有利有弊，如果想要在数组中插入或者删除一个元素，为了保障数组的内存空间的间断，就不免要挪动其余元素。

例如要删除下标为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 = 9print(twoSum(nums,target))

咱们能够看到该算法的工夫复杂度是O(n)，空间复杂度也是O(n)。

优化

当咱们须要枚举数组中的两个元素时，如果咱们发现随着第一个元素的递增，第二个元素是递加的，那么就能够应用双指针的办法，将枚举的工夫复杂度从O(N^2)减低到O(N)。所以咱们能够采纳双指针法来求解。首先，咱们先对数组进行排序，而后用left和right指针别离指向数组的右边和左边，此时sum=nums[left]+nums[right]，依据sum和target的大小关系，咱们来挪动指针。

如果sum>target，右指针左移，减小sum的值，即right=right-1。
如果sum<target，左指针右移，增大sum的值，即left=left+1。
如果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的窗口在序列上滑来滑去。

在理论的应用中，咱们应用的滑动窗口都是可变长度的。

咱们能够应用双指针来保护窗口的开始和完结，通过挪动左、右指针来实现窗口大小的扭转和窗口的滑动。

咱们来看一下题目，题目是求最长无反复元素子数组，如果咱们能够求出所有的无反复元素的子数组，那取出最长的不就好了。上面咱们来看一下如何求解。咱们只须要保护一个在数组中进行滑动的窗口就好。

开始时2不在窗口中，所以扩充窗口。

下一个元素2在窗口中呈现，所以咱们要将呈现过的元素及其右边的元素通通移出窗口，即2。

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

下一个元素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别离指向两个数组的起始地位，而后比拟大小，将较小的放入后果中，而后指针后移，直到将所有元素都排好序。

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

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[:] = sortednums1 = [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的后半局部是空的，能够间接笼罩而不会影响后果，所以这里引入了逆向双指针法。

咱们来看一下代码实现。

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]即可。因为题目要求所求的三元组是不反复的，所以须要判断去掉反复解。反复解次要有以下两种状况。

当nums[first]=nums[first-1]，因为咱们曾经把第一个元素是nums[first-1]的三元组曾经求解过了，所以没必要反复求解。
当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 resultnums=[-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_keydata=[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，这是因为：

当n1等于x时，对消的所有数字中，有一半是众数x。
当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)。

顺时针旋转数组

问题形容

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度旋转后，呈现在了倒数第一列的地位上，如下图所示。

并且，第一行的第 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]元素就被笼罩了，这显然不是咱们要的后果。

当晓得了如何原地旋转矩阵之后，这里还有一点须要明确：咱们应该选取哪些地位进行上述的原地替换操作呢？通过下面的剖析能够晓得，一次能够原地替换四个地位，所以：

当n为偶数时，咱们须要选取 n^2 / 4 = (n/2) * (n/2)个元素进行原地替换操作，能够将该图形分为四块，能够保障不反复、不脱漏旋转所有元素；
当n为奇数时，因为核心的地位通过旋转后地位不变，咱们须要选取 (n^2-1)/4=(n-1)/2 (n+1) /2个元素进行原地替换操作，咱们以55的矩阵为例，能够依照以下形式划分，进而保障不反复、不脱漏的旋转所有元素。

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

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。

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

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。

取区间[l，r]的中点，即mid=(l+r)/2。
如果下标mid是峰值，间接返回。
如果nums[mid] < nums[mid+1]，示意峰值在mid的左边，所以摈弃区间[l，mid]，在残余的[mid+1，r]的区间内去寻找。
如果nums[mid] > nums[mid+1]，示意峰值在mid的右边，所以摈弃区间[mid, r]，在残余的[l，mid-1]的区间内去寻找。

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

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

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。

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

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

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

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

合成：假如待排序的区间为[l,r]，咱们令mid=(l+r)//2，将区间分成[l,mid]和[mid+1,r]两局部。
解决：应用归并排序递归的求解两个子序列，使其有序。
合并：把两个曾经排好序的子序列[l,mid]和[mid+1,r]合并起来。

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

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

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

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中的数据由（A₀ A₁……A_n-1 ）变换为（A_n-m…… A_n-1 A₀ A₁……A_n-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]区间的元素，即能失去最初的答案。

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

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]

剖析问题

这道题咱们能够应用双指针法来求解，具体思路如下。

首先，申请两个指针i和j，别离指向数组nums的左右两端，即i=0，j=n-1。
当i所指的地位为奇数时，执行i=i+1，直到遇到偶数。
当j所指的地位为偶数时，执行j=j-1，直到遇到奇数。
而后替换nums[i]和nums[j]的值
反复上述操作，直到i==j为止。

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

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列的元素能够示意为C_i,j=A_i,1 B_1,j + A_i,2 B_2,j + ... + A_i,n B_n,j , 即等于A的第i行和B的第j列对应元素的乘积之和。

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

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

因为操作系统加载数据到缓存中时，都是把命中数据左近的一批数据一起加载到缓存中，因为操作系统认为如果一个内存地位被援用了，那么程序很可能在不久的将来援用左近的一个内存地位。所以咱们通过调整数组的读取程序来进行优化，使得矩阵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有多个，那么他们必定是连在一起的，所以咱们能够通过二次二分查找，别离寻找目标值所在范畴的上界和下界。首先，咱们来看一下上界和下界的定义。

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

上面咱们来看一下代码实现。

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

剖析问题

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

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

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

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

最初

原创不易！各位小伙伴感觉文章不错的话，无妨点赞（在看）、留言、转发三连走起！

你晓得的越多，你的思维越宽阔。咱们下期再见。