简介：算法篇-数组与矩阵。

　　　　知君何事泪纵横，断肠声里忆平生。

一、数组中重复sql教程的数字

1、题目描述

在一个长度为 n 的数组里的所有java基础教程数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重python基础教程复几次。请找出数组中任意一个重复的数字。

输入：[2,3,1,0,2,5,3]

输出：2

2、解题思路

要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能java基础教程使用排序的方法，也不能使用额外的标记数组。

对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为sql教程 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 }

 二、二维数组中的查找

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 }

三、替换空格

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 }

四、顺时针打印矩阵

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 }

五、第一个只出现一次的字符位置

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 }