数组与矩阵
# 3. 数组中重复的数字
# 题目链接
牛客网(opens new window) (opens new window)
# 题目描述
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
Input:
{2, 3, 1, 0, 2, 5}
Output:
2
2
3
4
5
# 解题思路
要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。
对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。
以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复：
public int duplicate(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
swap(nums, i, nums[i]);
}
swap(nums, i, nums[i]);
}
return -1;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 4. 二维数组中的查找
# 题目链接
牛客网(opens new window) (opens new window)
# 题目描述
给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
Consider the following 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]
]
Given target = 5, return true.
Given target = 20, return false.
2
3
4
5
6
7
8
9
10
11
# 解题思路
要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来快速地缩小查找区间，每次减少一行或者一列的元素。当前元素的查找区间为左下角的所有元素。
public boolean Find(int target, int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return false;
int rows = matrix.length, cols = matrix[0].length;
int r = 0, c = cols - 1; // 从右上角开始
while (r <= rows - 1 && c >= 0) {
if (target == matrix[r][c])
return true;
else if (target > matrix[r][c])
r++;
else
c--;
}
return false;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 5. 替换空格
# 题目链接
牛客网(opens new window) (opens new window)
# 题目描述
将一个字符串中的空格替换成 "%20"。
Input:
"A B"
Output:
"A%20B"
2
3
4
5
# 解题思路
① 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。
② 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。
③ 当 P2 遇到 P1 时（P2 <= P1），或者遍历结束（P1 < 0），退出。
public String replaceSpace(StringBuffer str) {
int P1 = str.length() - 1;
for (int i = 0; i <= P1; i++)
if (str.charAt(i) == ' ')
str.append(" ");
int P2 = str.length() - 1;
while (P1 >= 0 && P2 > P1) {
char c = str.charAt(P1--);
if (c == ' ') {
str.setCharAt(P2--, '0');
str.setCharAt(P2--, '2');
str.setCharAt(P2--, '%');
} else {
str.setCharAt(P2--, c);
}
}
return str.toString();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 29. 顺时针打印矩阵
# 题目链接
牛客网(opens new window) (opens new window)
# 题目描述
按顺时针的方向，从外到里打印矩阵的值。下图的矩阵打印结果为：1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10
# 解题思路
一层一层从外到里打印，观察可知每一层打印都有相同的处理步骤，唯一不同的是上下左右的边界不同了。因此使用四个变量 r1, r2, c1, c2 分别存储上下左右边界值，从而定义当前最外层。打印当前最外层的顺序：从左到右打印最上一行->从上到下打印最右一行->从右到左打印最下一行->从下到上打印最左一行。应当注意只有在 r1 != r2 时才打印最下一行，也就是在当前最外层的行数大于 1 时才打印最下一行，这是因为当前最外层只有一行时，继续打印最下一行，会导致重复打印。打印最左一行也要做同样处理。
public ArrayList<Integer> printMatrix(int[][] matrix) {
ArrayList<Integer> ret = new ArrayList<>();
int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
// 上
for (int i = c1; i <= c2; i++)
ret.add(matrix[r1][i]);
// 右
for (int i = r1 + 1; i <= r2; i++)
ret.add(matrix[i][c2]);
if (r1 != r2)
// 下
for (int i = c2 - 1; i >= c1; i--)
ret.add(matrix[r2][i]);
if (c1 != c2)
// 左
for (int i = r2 - 1; i > r1; i--)
ret.add(matrix[i][c1]);
r1++; r2--; c1++; c2--;
}
return ret;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 50. 第一个只出现一次的字符位置
# 题目链接
牛客网(opens new window) (opens new window)
# 题目描述
在一个字符串中找到第一个只出现一次的字符，并返回它的位置。字符串只包含 ASCII 码字符。
Input: abacc
Output: b
2
# 解题思路
最直观的解法是使用 HashMap 对出现次数进行统计：字符做为 key，出现次数作为 value，遍历字符串每次都将 key 对应的 value 加 1。最后再遍历这个 HashMap 就可以找出出现次数为 1 的字符。
考虑到要统计的字符范围有限，也可以使用整型数组代替 HashMap。ASCII 码只有 128 个字符，因此可以使用长度为 128 的整型数组来存储每个字符出现的次数。
public int FirstNotRepeatingChar(String str) {
int[] cnts = new int[128];
for (int i = 0; i < str.length(); i++)
cnts[str.charAt(i)]++;
for (int i = 0; i < str.length(); i++)
if (cnts[str.charAt(i)] == 1)
return i;
return -1;
}
2
3
4
5
6
7
8
9
以上实现的空间复杂度还不是最优的。考虑到只需要找到只出现一次的字符，那么需要统计的次数信息只有 0,1,更大，使用两个比特位就能存储这些信息。
public int FirstNotRepeatingChar2(String str) {
BitSet bs1 = new BitSet(128);
BitSet bs2 = new BitSet(128);
for (char c : str.toCharArray()) {
if (!bs1.get(c) && !bs2.get(c))
bs1.set(c); // 0 0 -> 0 1
else if (bs1.get(c) && !bs2.get(c))
bs2.set(c); // 0 1 -> 1 1
}
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (bs1.get(c) && !bs2.get(c)) // 0 1
return i;
}
return -1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16