数组题目技巧总结（二）

数组题目介绍

数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍数组与排序结合的问题。

问题类型与技巧

1. 直接对数组排序

   这类题目可能是题目本身要求就是要对数组进行排序，也有可能是需要经过排序在有序数组上才能解决问题。一般排序可以选择sort函数（可能需要重载比较），也可以自己写其他排序方法。

2. 利用各类排序思想解决数组问题

   这类题目主要是利用快排、归并排序等排序方法的思想，来使数组有序，或者获取与次序有关的信息。一般归并排序思想出现于有两个数组的情况。

经典题型

• 题目①合并两个有序的数组

  这道题目属于上述问题第二点，因为两个数组本来就是有序的，这正好符合归并排序合并阶段的两个子数组，因此可以按照归并排序的思想，依次拿出最小值。但是因为这道题只能在原数组上修改，而数组A末尾有多余的空间，所以还是一个变体，不是依次拿出最小值，而是依次拿出最大值放入数组A末尾。

• 题目②合并区间

  这道题属于上述问题第一点，给定的区间都是无序的，而题目要求输出必须按照区间起点非降序排列，那我们就需要对区间按照起点位置进行一次排序，这里选择sort函数和重载比较方式。而正好排序后的区间可以使用贪心算法完成合并。

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

  这道题属于上述问题第二点，还是给出两个有序的数组，要找到2n个数字中的第n小，可以使用归并排序的思想，依次取出前n-1个最小值，然后再取出的最小值就是上中位数。

• 题目④数组中的最长连续子序列

  这道题属于上述问题第一点，题目要求最长的连续子序列，即数字相连的最大长度，那很明显对无序数组排序后相连的数字在数组中都是相邻的（不过要注意重复数字），一旦相连断掉，排序后的数组也很明晰。因此排序能更便于解决这道题。

• 题目⑤数组中的逆序对

  这道题乍一看与排序无关，但是却是用归并排序的思想解决问题：想要直接逐个统计逆序对复杂度过高，利用归并排序右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。