排序与查找
排序与查找是算法的基础，面试中经常考察各种排序算法的实现、二分查找的应用以及搜索优化技巧。
面试题 10.01. 合并排序的数组
题目描述
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法，将 B 合并入 A 并排序。初始化 A 和 B 的元素数量分别为 m 和 n。
示例：
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
解题思路
从后向前合并，避免移动元素。使用三个指针，分别指向 A 和 B 的末尾以及合并后的末尾。
Java 代码实现
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (A[i] > B[j]) {
A[k--] = A[i--];
} else {
A[k--] = B[j--];
}
}
while (j >= 0) {
A[k--] = B[j--];
}
}
}
面试题 10.02. 变位词组
题目描述
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
示例：
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
解题思路
使用哈希表，将排序后的字符串作为 key，将同组变位词存储在同一个列表中。
Java 代码实现
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
}
面试题 10.03. 搜索旋转数组
题目描述
搜索旋转数组。给定一个排序后的数组，包含 n 个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
示例 1：
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素 5 在该数组中的索引）
示例 2：
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出: -1
解题思路
修改的二分查找。需要判断哪半边是有序的，然后判断目标值是否在有序的那半边。
Java 代码实现
class Solution {
public int search(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
while (mid > 0 && arr[mid - 1] == target) {
mid--;
}
return mid;
}
if (arr[left] < arr[mid]) {
if (arr[left] <= target && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (arr[left] > arr[mid]) {
if (arr[mid] < target && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
left++;
}
}
return -1;
}
}
面试题 10.05. 稀疏数组搜索
题目描述
稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
示例 1：
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""], s = "ta"
输出：-1
示例 2：
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""], s = "ball"
输出：4
解题思路
修改的二分查找。当中间元素为空字符串时，向两边寻找最近的非空字符串作为 mid。
Java 代码实现
class Solution {
public int findString(String[] words, String s) {
int left = 0, right = words.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
while (mid < right && words[mid].equals("")) {
mid++;
}
if (words[mid].equals("")) {
right = left + (right - left) / 2 - 1;
continue;
}
int cmp = words[mid].compareTo(s);
if (cmp == 0) {
return mid;
} else if (cmp < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
面试题 10.09. 排序矩阵查找
题目描述
给定 M×N 矩阵，每一行、每一列都按升序排列，请编写代码快速找出某元素。
示例：
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
解题思路
从矩阵的右上角或左下角开始搜索。如果当前元素大于目标值，向左移动；如果小于目标值，向下移动。
Java 代码实现
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}
}
面试题 10.10. 数字流的秩
题目描述
假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：
实现 track(int x) 方法，每读入一个数字时调用该方法。
实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。
示例：
输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]
解题思路
使用二叉搜索树或树状数组。每个节点记录左子树的节点数量，这样可以在 O(log n) 时间内获取秩。
Java 代码实现
class StreamRank {
private TreeNode root;
public StreamRank() {
}
public void track(int x) {
root = insert(root, x);
}
public int getRankOfNumber(int x) {
return getRank(root, x);
}
private TreeNode insert(TreeNode node, int x) {
if (node == null) {
return new TreeNode(x);
}
if (x <= node.val) {
node.leftSize++;
node.left = insert(node.left, x);
} else {
node.right = insert(node.right, x);
}
return node;
}
private int getRank(TreeNode node, int x) {
if (node == null) {
return 0;
}
if (x == node.val) {
return node.leftSize;
} else if (x < node.val) {
return getRank(node.left, x);
} else {
return node.leftSize + 1 + getRank(node.right, x);
}
}
class TreeNode {
int val;
int leftSize;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
}
面试题 10.11. 峰与谷
题目描述
在一个整数数组中，"峰"是大于或等于相邻整数的元素，"谷"是小于或等于相邻整数的元素。例如，在 {5, 8, 6, 2, 3, 4, 6} 中，{8, 6} 是峰，{5, 2} 是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。
示例：
输入: [5,3,1,2,3]
输出: [5,2,3,1,3]
解题思路
遍历数组，对于偶数位置，确保它比相邻元素大（峰）；对于奇数位置，确保它比相邻元素小（谷）。如果不满足条件，则交换。
Java 代码实现
class Solution {
public void wiggleSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if ((i % 2 == 1 && nums[i] < nums[i - 1]) ||
(i % 2 == 0 && nums[i] > nums[i - 1])) {
int temp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = temp;
}
}
}
}