剑指OFFER练习记录(一. 数组部分)
这是自己刷题的笔记, 有Java和Python的实现, 尽量每一题都挑选典型的方法进行记录. 题目的分类是按照牛客平台分类的.
二维数组中的查找
题目:
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路(二分查找):
- 我们把初始坐标定位在右上角[i, j], 根据排序特性, 此时指向的数比左边的数大, 比下面的数小.
- 查找目标数记录为target, 如果target < arr[i, j], 则target若在arr中存在, 只可能在[i, j]位置的坐标的左边; 如果target > arr[i, j], 则target只可能在[i, j]位置的下边.
public class Solution {
public boolean Find(int target, int[][] array) {
if (array.length == 0 || array[0].length == 0) {
return false;
}
int endX = array.length - 1;
int endY = array[0].length - 1;
int x = 0;
int y = endY;
while (x <= endX && y >= 0) {
if (target == array[x][y]) {
return true;
} else if (target < array[x][y]) {
y--;
} else if (target > array[x][y]) {
x++;
}
}
return false;
}
}
class Solution:
def Find(self, target, array):
if array is None or array[0] is None:
return False
end_x, end_y = len(array) - 1, len(array[0]) - 1
x, y = 0, end_y
while x <= end_x and y >= 0:
if target == array[x][y]:
return True
elif target < array[x][y]:
y -= 1
else:
x += 1
return False
数组中重复的数字
题目:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路(哈希):
利用哈希集合收集数组中出现过的数, 在遍历数组过程中对从哈希表进行检查即可. 这种方法的额外空间复杂度为O(n)
import java.util.HashSet;
public class Solution {
public boolean duplicate(int numbers[], int length, int[] duplication) {
if (length == 0) return false;
HashSet<Integer> set = new HashSet<>();
for (int i : numbers) {
if (set.contains(i)) {
duplication[0] = i;
return true;
} else {
set.add(i);
}
}
duplication[0] = -1;
return false;
}
}
class Solution:
def duplicate(self, numbers, duplication):
duplication[0] = -1
if len(numbers) == 0:
return False
my_set = set()
for i in numbers:
if i in my_set:
duplication[0] = i
return True
else:
my_set.add(i)
return False
构建乘积数组
题目: 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
思路(两个数组存放当前位置以前的累乘和当前位置以后的累乘积):
- 从尾遍历数组, 对于每个位置i, 都记录该数之后的数的累乘(不包括i位置的数)
- 从头遍历数组, 对于每个位置i, 都记录包括该数之前的数的累乘(不包括i位置的数)
- 把两个数组对应位置的数乘起来
class Solution {
public int[] multiply(int[] A) {
if (A.length == 0) return new int[0];
int[] tmp = new int[A.length];
int[] res = new int[A.length];
tmp[A.length - 1] = 1;
for (int i = A.length - 2; i >= 0; i--) {
tmp[i] = A[i + 1] * tmp[i + 1];
}
int cur = 1;
for (int i = 1; i < A.length; i++) {
// 只需要一个遍历记录累乘的数
cur *= A[i - 1];
res[i] = cur * tmp[i];
}
res[0] = tmp[0];
return res;
}
}
class Solution:
def multiply(self, A):
tmp = [1 for i in range(len(A))]
res = []
for i in range(len(A) - 2, -1, -1):
tmp[i] = A[i + 1] * tmp[i + 1]
cur = 1
res.append(tmp[0])
for i in range(1, len(A), 1):
cur *= A[i - 1]
res.append(cur * tmp[i])
return res
