最近打算按照LeetCode的标签来做一些题目，有些题目可能属于多个标签，比如一个题目既可能是数组相关，又可能是双指针相关，我想先打算做刷前300题，刷完前三百，再做后面三百，这样每个 标签的可能有十几道题目，这篇文章用来记录排序相关题目的一些思路，往往不涉及完整代码。
56、合并所有重叠的区间
示例 1:
// 输入: [[1,3],[2,6],[8,10],[15,18]]
//输出: [[1,6],[8,10],[15,18]]
//解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
这个题目我一下就想到了，需要将输入的所有区间排序，按照区间的左端点从大到小排序，你可以想一下，如果不排序，每次处理一个待排序区间的时候，都需要去遍历当前已经合并好的所有区间， 去找一个合适的位置把他们合并，这里的情况就会比较复杂。
将待合并的区间，按照其左端点大小排序后，情况就比较简单了，也就是在完成这句话以后，Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]))。遍历待排序的区间 集合，如果新加入区间的左端点大于合并好的区间列表的最后一个区间的右端点，那么直接将新区间加入合并好的区间列表即可；否则，则直接更新合并好的区间列表的最后一个区间的右端点，更新成 什么呢？只需要判断新加入区间的右端点和合并好的区间列表的最后一个区间的右端点的大小即可，更新为更大的那个。
这里要理解，为什么可以这么做？本质上是因为前面那次排序，已经帮你处理了很多复杂情况了。
57、插入区间
// 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
// 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
// 示例 1：
//
// 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
//输出：[[1,5],[6,9]]
//
// 示例 2：
//
// 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
//输出：[[1,2],[3,10],[12,16]]
这个题目标的是一道hard，但实际上和上一道题目是一道题，不过稍微有点变化。上一道题目是对所有区间进行合并，这一道题目是已经给了一个有序的，无重叠的区间集合，将一个新的区间插入到这个集合中，最笨的 方法就是转化为上一道题目，先将新区间放到集合的末尾，然后对其按左端点排序，再进行合并，这是最笨的方法了。
这种区间的题目，做法都还是比较接近的，遍历当前列表，然后判断当前区间和 新的区间是否有交集：1、如果新加入区间的左端点都大于当前区间的右端点的话，那么跟当前区间必然不会有任何交集，直接将当前区间加 入最终结果中即可；2、新加入区间的右端点都小于，当前区间的左端点，那么跟当前区间也没有任何交集，而且新区间可以认为是"小于"当前区间的，那么按照顺序，应该先把新区间加入列表，然后把当前区间加入列表，而且 注意，一旦新区间被加入结果集合中后，就应该被置空了；3、最后一种情况就是，当前区间和新区间是有交集的，这种就是更新一下新区间的左右端点即可，这里就相当于是将当前遍历到的区间和新区间进行了合并，当前区间 就可以忽略了，但是，合并后的区间还可能和后续的区间有交集，所以这里不能直接将新区间加入结果中。看下代码还是可以理解的。
75、给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列
// 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
//
// 注意:
//不能使用代码库中的排序函数来解决这道题。
//
// 示例:
//
// 输入: [2,0,2,1,1,0]
//输出: [0,0,1,1,2,2]
这个题，提示的就比较简单了。先遍历一遍，分别记录下0、1、2的个数，第二次遍历，根据次数，将数组的元素赋相应 的值即可，总共两次遍历，不过题目中提示了是否有只一次遍历的方式。
另一种简单的方法是双指针法，用两个指针left和right，初始化分别指向数组的第一个元素和最后一个元素，left指针 永远指向最后一个非0的元素，right指针指向的是第一个非2的元素。然后遍历数组，如果当前元素是0，则和left指向的元 素进行交换，left指针自增，继续遍历下一个元素（i++）；如果当前元素是2，则和right指针指向的元素交换，right指针 自减，但是这里需要注意的是，从后面换过来的这个元素，还没有判断它的值是多少，因此这时不能继续遍历下一个元素 （没有i++）；如果当前元素是1，则继续遍历下一个元素，left和right均不动。这个是其核心。
148、在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
这个题目和第147题差不多，147题要求使用插入排序对一个链表排序，这道题目只要求在一定的时间复杂度下对链表进行排序，看到这个时间复杂度，很容易就想到了归并排序的思路，这个题目可以和合并两个有序链表 结合起来，但是如何使得链表本身有序呢又？这就是一个递归的过程。我们可以通过快慢指针法找到链表的中间节点，然后递归的找中间节点，对其进行合并。
本质上，这是一道 找链表中间节点 + 合并两个有序链表 + 递归的题目，尤其递归的思路需要好好思考。
164、给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值
// 如果数组元素个数小于 2，则返回 0。
//
// 示例 1:
//
// 输入: [3,6,9,1]
//输出: 3
//解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
这个题目要求的是在线性的时间复杂度和空间复杂度下进行求解，也就是说，肯定不能用常规的先个排序，再遍历计算的方式，因为常规的快排时间复杂度也就是O(n×log(n))，所以题目的核心是在考察你能不能写出 线性时间复杂度的排序算法，也就是传说中的基数排序和桶排序。这两种排序，在王争的数据结构与算法之美中都有提到。
基数排序就是，我们先将待排序的每个数都对齐，通过补0的方式使其位数一致，然后初始化10个集合，从最低位开始，分别将该位置 值等于某个数字的，放置到对应的集合中，一轮过后，按照0-9的顺序将这些数字取出，重新构成一个"最低位已经有序的"数组，继续第二 轮，按照倒数第二位的数字，进行放置。重复这个过程，直到最后得到的序列即是有序的。写这个排序过程的代码也有很多细节需要注意，首先需要提前构建一个二维列表，里面每一个元素用来存储当前遍历位等于 该index的数字，需要遍历多少次呢？应该是待排序数组中最大元素的位数那么多次，在遍历的过程中，依次放到相应的list里，然后重新取出来，依次放回原数组中，开启下一轮的遍历，细则较多！
attention：这道题还有一种桶排序的方法，时间复杂度比前面的基数排序还要低一些，但是我还没有充分理解。
179、给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数
// 示例 1:
//
// 输入: [10,2]
//输出: 210
//
// 示例 2:
//
// 输入: [3,30,34,5,9]
//输出: 9534330
//
// 说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
先来看一个简单的，34和3组成的字符串结果，343是大于334的，也就是需要把34排前面，3排后面，所以我们可以先对这个数组进行排序，排序的原则就是，两个字符串拼接起来，字典序更大的那个符合排序规则，即 这样一行代码：Arrays.sort(strArray, (o1, o2) -> (o2 + o1).compareTo(o1 + o2)); 将整个数组排好序以后，再拼接起来就是最大的整数了。
220、在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums[i] 和 nums[j] 的差的绝对值小于等于t，且满足 i 和 j 的差的绝对值也小于等于k
// 示例 1:
//
// 输入: nums = [1,2,3,1], k = 3, t = 0
//输出: true
//
// 示例 2:
//
// 输入: nums = [1,0,1,1], k = 1, t = 2
//输出: true
这个题最直观的一种解法是，两个for循环，在进行判断即可，这里的一个不容易发现的边界条件是，在两个int数相减的时候，是可能发生溢出的，比如2147483647和-1相减，得到的结果是-2147483648，因为这 是最小的int数，而最大的int数是2147483647，所以这里需要注意一下，可以用Math.abs((long) nums[i] - nums[j]) <= t这样的方式来避免int溢出，但是很遗憾，两次循环是会超时的。
这个题的标准答案解法是，利用一个有序的TreeSet，一次遍历数组中的元素，通过控制set的大小，来进行查找。这里需要用到的是TreeSet的一些特殊方法，ceiling(E e)返回的是大于等于e的最小的那个元素， 代码上比较简洁但是并不算容易理解，需要回顾并记住。
242、给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词
// 示例 1:
//
// 输入: s = "anagram", t = "nagaram"
//输出: true
//
//
// 示例 2:
//
// 输入: s = "rat", t = "car"
//输出: false
//
// 说明:
//你可以假设字符串只包含小写字母。
这道题目，只要理解清楚了题意，并不算难。先看一下字母异位词的解释：两个字符串长度需要相等，其中每个字符出现的次数也需要相等，但是顺序可以不同，比如"car"和"car"是字母异位词，即使它们完全一样。 有了这个定以后，这个题目就比较好做了，用一个map记录字符串s中每个字符的出现次数，然后在遍历第二个字符串的时候，同时去map中查找，如果没有找到那直接返回false，如果查找到了，那将个数减一，继续遍历 查找即可，属于easy题目。
242、给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的h指数
// h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引
//用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）
//
// 例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。
// 示例：
//
// 输入：citations = [3,0,6,1,5]
//输出：3
//解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
// 由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
这个题，我一开始搞复杂了一点，导致很多边界条件的case过不去，也是需要先对数组排个序，但是我一开始有点傻的还使用了一个map来记录每个数字的index，然后通过查找map中的index来判断大于等于当前这个 数字的元素个数是多少，但是在碰到0的case的时候，一直过不去，还是去翻了答案。
先排序一次没有太多说的，答案更为简洁，直接使用了一个论文序号，第几篇，从后往前遍历排好序的数组，直到某篇论文的序号大于该论文被引次数。所得序号减一即为H指数。看代码其实还比较容易理解，需要注意 的是序号从1开始，遍历是倒着遍历的（因为前面排序默认是升序）。