数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的
- 数组的元素是不能删的，只能覆盖。
正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
Java 二维数组内存排列
二分查找
704. 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
// 防止溢出 等同于(left + right)/2
int mid = (right - left) / 2 + left;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
|
二分查找的做法是，定义查找的范围 [left,right]，初始查找范围是整个数组。每次取查找范围的中点 mid，比较 nums[mid] 和 target 的大小，如果相等则 mid 即为要寻找的下标，如果不相等则根据 nums[mid] 和 target 的大小关系将查找范围缩小一半。
由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 $O(logn)$，其中 n 是数组的长度。空间复杂度：$O(1)$。
写二分法，区间的定义一般为两种
- 左闭右闭即[left, right]，while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- 左闭右开即[left, right)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public int search(int[] nums, int target) {
// 定义target在左闭右开的区间里，即：[left, right) right 不需要 -1
int left = 0, right = nums.length;
// 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
while (left < right) {
// 防止(left + right)溢出 等同于(left + right)/2
int mid = (right - left) / 2 + left;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
right = mid;
} else {
left = mid + 1;
}
}
return -1;
}
}
|
搜索插入位置
35. 搜索插入位置
考虑这个插入的位置 pos，它成立的条件为：
$nums[pos−1]<target≤nums[pos]$
在一个有序数组中找第一个大于等于 target 的下标，直接套用二分法即可，即不断用二分法逼近查找第一个大于等于 target 的下标 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
|
27. 移除元素
27. 移除元素
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组更新慢指针的值及+1
慢指针：指向更新 新数组下标的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
}
|
977. 有序数组的平方
977. 有序数组的平方
1
2
3
4
|
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
|
1
2
3
4
5
6
7
8
9
10
|
class Solution {
public int[] sortedSquares(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
ans[i] = nums[i] * nums[i];
}
Arrays.sort(ans);
return ans;
}
}
|
时间复杂度 $O(nlogn)$ 空间复杂度 $O(logn)$ 的栈空间进行排序。
双指针 使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[pos] = nums[i] * nums[i];
++i;
} else {
ans[pos] = nums[j] * nums[j];
--j;
}
--pos;
}
return ans;
}
}
|
- 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
- 空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。
209. 长度最小的子数组
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
滑动窗口
累加快指针指向的数值并移动 直到 sum >= s；减去慢指针指向的数值并移动直到 sum >= s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
// 前缀和
sum += nums[end];
while (sum >= s) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
|
前缀和 + 二分查找
因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的。
为了使用二分查找，需要额外创建一个数组 sums 用于存储数组 nums 的前缀和，其中 sums[i] 表示从 nums[0] 到 nums[i−1] 的元素和。得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于 i 的最小下标 bound，使得 $sums[bound]−sums[i−1]≥s$，并更新子数组的最小长度（此时子数组的长度是 bound−(i−1)）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int[] sums = new int[n + 1];
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= n; i++) {
int target = s + sums[i - 1];
int bound = Arrays.binarySearch(sums, target);
if (bound < 0) {
bound = -bound - 1;
}
if (bound <= n) {
ans = Math.min(ans, bound - (i - 1));
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
|
螺旋矩阵 II
59. 螺旋矩阵 II
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
27
28
29
30
31
32
|
class Solution {
public int[][] generateMatrix(int n) {
int num = 1;
int[][] matrix = new int[n][n];
int left = 0, right = n - 1, top = 0, bottom = n - 1;
while (left <= right && top <= bottom) {
for (int column = left; column <= right; column++) {
matrix[top][column] = num;
num++;
}
for (int row = top + 1; row <= bottom; row++) {
matrix[row][right] = num;
num++;
}
if (left < right && top < bottom) {
for (int column = right - 1; column > left; column--) {
matrix[bottom][column] = num;
num++;
}
for (int row = bottom; row > top; row--) {
matrix[row][left] = num;
num++;
}
}
left++;
right--;
top++;
bottom--;
}
return matrix;
}
}
|
