一、剑指 Offer 04. 二维数组中的查找
要求：在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：可以暴力，但是时间复杂度O(mn)太高。
可以从矩阵的右上角上开始看，把矩阵看成是一个排序二叉树，左边的值都是比节点小的，右边的值都是比节点大的。通过排序二叉树实现快速查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public static boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix.length==0||matrix[0].length==0){
return false;
}
int row = 0;
int column = matrix[0].length - 1;
while (row <= matrix.length - 1 && column >= 0) {
int node = matrix[row][column];
if(node > target){
column--;
}else if(node < target){
row++;
}else{
return true;
}
}
return false;
}
}
|
二、剑指 Offer 11. 旋转数组的最小数字
要求：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。
思路：使用二分查找，当mid的值和end的值相同时，暴力的将end值右移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int minArray(int[] numbers) {
int left = 0;
int right = numbers.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (numbers[mid] < numbers[right]) {
right = mid;
} else if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else {
right -= 1;
}
}
return numbers[left];
}
}
|
三、剑指 Offer 50. 第一个只出现一次的字符
要求：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
解法1：使用hashmap存储索引，遍历两次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public static char firstUniqChar(String s) {
if(s.equals("")){
return " ".charAt(0);
}
HashMap<String,Integer> charList = new HashMap<>();
String[] strArr = s.split("");
for(String element :strArr){
if(!charList.containsKey(element)){
charList.put(element,0);
}else{
charList.put(element,1);
}
}
for(String each : strArr){
if(charList.get(each)==0){
return each.charAt(0);
}
}
return " ".charAt(0);
}
|
好理解，但是两次循环，时间复杂度高。官方解法没用split，直接对s使用charAt遍历，更快一点。
解法2：省略了split
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static char firstUniqChar(String s) {
if(s.equals("")){
return " ".charAt(0);
}
HashMap<Character,Integer> charList = new HashMap<>();
for(int i = 0; i < s.length(); i++){
if(!charList.containsKey(s.charAt(i))){
charList.put(s.charAt(i),0);
}else{
charList.put(s.charAt(i),1);
}
}
for(int j = 0; j < s.length();j++){
if(charList.get(s.charAt(j))==0){
return s.charAt(j);
}
}
return " ".charAt(0);
}
|
