算法-数组与矩阵
算法-数组与矩阵
简介：算法篇-数组与矩阵。
知君何事泪纵横，断肠声里忆平生。
一、数组中重复的数字
1、题目描述
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
输入：[2,3,1,0,2,5,3]
输出：2
2、解题思路
要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。
对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。
以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复：
3、代码示例
- 1 import java.util.*;
- 2
- 3 public class Solution {
- 4 public int duplicate (int[] numbers) {
- 5 int length = numbers.length;
- 6 if(length == 0 || length ==1){
- 7 return -1;
- 8 }
- 9 Arrays.sort(numbers); // 利用Arrays从小到大排序
- 10 for(int i = 0; i < length -1; i++){
- 11 if(numbers[i] == numbers[i + 1]){
- 12 return numbers[i];
- 13 }
- 14 }
- 15 return -1;
- 16 }
- 17 }
View Code
二、二维数组中的查找
1、题目描述
给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
输出：true
2、解题思路
要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来快速地缩小查找区间，每次减少一行或者一列的元素。当前元素的查找区间为左下角的所有元素。
3、代码示例
- 1 public class Solution {
- 2 public boolean Find(int target, int [][] array) {
- 3 boolean flag = false;
- 4 for(int i = 0; i < array.length; i++){
- 5 for(int j = 0; j < array[i].length; j++){
- 6 if(array[i][j] == target){
- 7 flag = true;
- 8 break;
- 9 }
- 10 }
- 11 if(flag){
- 12 break;
- 13 }
- 14 }
- 15 return flag;
- 16 }
- 17 }
View Code
三、替换空格
1、题目描述
将一个字符串中的空格替换成 “%20″。
输入：”We Are Happy”
输出：”We%20Are%20Happy”
2、解题思路
① 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。
② 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。
③ 当 P2 遇到 P1 时（P2 <= P1），或者遍历结束（P1 < 0），退出。
3、代码示例：
- 1 import java.util.*;
- 2
- 3
- 4 public class Solution {
- 5
- 6 public String replaceSpace (String s) {
- 7 return s.replace(" ", "%20");
- 8 }
- 9 }
View Code
四、顺时针打印矩阵
1、题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：
- [[1,2,3,4],
- [5,6,7,8],
- [9,10,11,12],
- [13,14,15,16]]
则依次打印出数字：
- [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
输入：[[1,2],[3,4]]
输出：[1,2,4,3]
2、解题思路
一层一层从外到里打印，观察可知每一层打印都有相同的处理步骤，唯一不同的是上下左右的边界不同了。因此使用四个变量 r1, r2, c1, c2 分别存储上下左右边界值，从而定义当前最外层。打印当前最外层的顺序：从左到右打印最上一行->从上到下打印最右一行->从右到左打印最下一行->从下到上打印最左一行。应当注意只有在 r1 != r2 时才打印最下一行，也就是在当前最外层的行数大于 1 时才打印最下一行，这是因为当前最外层只有一行时，继续打印最下一行，会导致重复打印。打印最左一行也要做同样处理。
3、代码示例
- 1 import java.util.ArrayList;
- 2
- 3 public class Solution {
- 4 public ArrayList<Integer> printMatrix(int [][] matrix) {
- 5 int n = matrix.length;
- 6 int m = matrix[0].length;
- 7 int left = 0;
- 8 int right = m - 1;
- 9 int top = 0;
- 10 int tail = n - 1;
- 11 ArrayList list = new ArrayList<>();
- 12 while(true){
- 13 for(int i = left; i <= right; i++){
- 14 list.add(matrix[top][i]);
- 15 }
- 16 if(++top > tail){
- 17 break;
- 18 }
- 19 for(int i = top; i <= tail; i++){
- 20 list.add(matrix[i][right]);
- 21 }
- 22 if(--right < left){
- 23 break;
- 24 }
- 25 for(int i = tail; i >= top; i--){
- 26 list.add(matrix[i][left]);
- 27 }
- 28 if(++left > right){
- 29 break;
- 30 }
- 31 }
- 32 return list;
- 33 }
- 34 }
View Code
五、第一个只出现一次的字符位置
1、题目描述
在一个字符串中找到第一个只出现一次的字符，并返回它的位置。字符串只包含 ASCII 码字符。
输入：”google”
输出：4
2、解题思路
最直观的解法是使用 HashMap 对出现次数进行统计：字符做为 key，出现次数作为 value，遍历字符串每次都将 key 对应的 value 加 1。最后再遍历这个 HashMap 就可以找出出现次数为 1 的字符。
考虑到要统计的字符范围有限，也可以使用整型数组代替 HashMap。ASCII 码只有 128 个字符，因此可以使用长度为 128 的整型数组来存储每个字符出现的次数。
3、代码示例
- 1 public class Solution {
- 2 public int FirstNotRepeatingChar(String str) {
- 3 for(int i = 0; i < str.length(); i++){
- 4 // str.charAt(i) 取ASC码
- 5 // str.indexOf(str.charAt(i)) 取ASC码第一次出现的索引下标位置
- 6 // str.lastIndexOf(str.charAt(i)) 取ASC码最后一次出现的
- 7 if(str.indexOf(str.charAt(i)) != str.lastIndexOf(str.charAt(i))){
- 8 continue;
- 9 }
- 10 return i;
- 11 }
- 12 return -1;
- 13 }
- 14 }
View Code
知君何事泪纵横
断肠声里忆平生