排序和查找

11.1 给定两个排序后的数组A和B，其中A的末端有足够的缓冲空容纳B。编写一个方法， 将B合并入A并排序。（第 77 页）

这么做的唯一问题是，如果将元素插入数组A的前端，就必须将原有的元素往后移动，以腾 出空间。更好的做法是将元素插入数组A的末端，那里都是空闲的可用空间。 下面的代码就实现了上述做法， 从数组A和B的末端元素开始， 将最大的元素放到数组A 的末端。

11.2 编写一个方法，对字符串数组进行排序，将所有变位词 ① 排在相邻的位置。（第 77 页）

Solution 1: Sort and Custom Comparator (count or sort chars)

Solution 2: 桶排序法 Map<key, List> key string after sort

11.3 给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次，次数不详。 请编写代码找出数组中的某个元素。可以假定数组元素原先是按从小到大的顺序排列的。（第 77 页）

二分查找法

数组有一半（左边或右边）必定是按正常顺序（升序） 排列的。

若所有元素都不同，则上述代码执行的时间复杂度为O(log n)。有很多元素重复的话，算法 时间复杂度则为O(n)。因为若有很多重复元素，数组（或子数组）的左半边和右半边往往都得 查找。

11.4 设想你有一个 20GB的文件，每一行一个字符串。请说明将如何对这个文件进行排 序。（第 77 页）
当面试官给出20GB大小的限制时，实际上在暗示些什么。就此题而言，这表明他们不希望 你将数据全部载入内存。

我们将把整个文件划分成许多块，每个块x MB，其中x是可用的内存大小。每个块各自进行 排序，然后存回文件系统。 各个块一旦完成排序，我们便将这些块逐一合并在一起，最终就能得到全都排好序的文件。 这个算法被称为外部排序（external sort）。

11.5 有个排序后的字符串数组，其中散布着一些空字符串，编写一个方法，找出给定字 符串的位置。（第 77 页）

如果没有那些空字符串，就可以直接使用二分查找法。比较待查找字符串str和数组的中间 元素，然后继续搜索下去。 针对数组中散布一些空字符串的情形，我们可以对二分查找法稍作修改，所需的修改就是与 mid进行比较的地方，如果mid为空字符串，就将mid换到离它最近的非空字符串的位置。

如果要查找空字符串，务必小心对待。我们该找出空字符串的位置（该操作时间复杂度为 O(n)）？还是应该把这种情形作为错误处理？

很遗憾，这里并没有正确的答案。关于这一点你应该与面试官进行讨论，只需简单地询问一 下，就能表明你是个细心的程序员。

11.6 给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。（第 77 页）

Solution 1: Binary Search Line by Line

Solution 2:

11.7 有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和 美观的考虑，在上面的人要比下面的人矮一点、轻一点。已知马戏团每个人的高度和重量，请编 写代码计算叠罗汉最多能叠几个人。（第 77 页）

Sort on one dimension, Then find longest increasing subsequence on this sort list's another dimension

11.8 假设你正在读取一串整数。每隔一段时间，你希望能找出数字x的秩（小于或等于x的 值的数目）。请实现数据结构和算法支持这些操作。也就是说，实现track(int x)方法，每读入 一个数字都会调用该方法；以及getRankOfNumber(int x)方法，返回值为小于或等于x的元素个 数（不包括x本身）。（第 77 页）

Solution 1: Use Array and Binary Search

Solution 2: BST. TreeNode Stores Val, and Rank