数组理论基础

  1. 数组是存放在连续内存空间上的相同类型数据的集合。

    image-20240522193029336

  • 数组下标都是从0开始的

  • 数组内存空间的地址是连续的(因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址

  1. 二维数组

    image-20240522193547234

    不同语言内存管理不同,C++中二维数组是连续分布的,Java 不是。

704. 二分查找

代码随想录

大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。(不是很理解)

第一种写法

定义 target 是在一个在左闭右闭的区间里,也就是[left, right] (这个很重要非常重要)

  • while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1

image-20240524103229994

第二种写法

target 是在一个在左闭右开的区间里,也就是**[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(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle; // target 在左区间,在[left, middle)中
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间,在[middle + 1, right)中
} else { // nums[middle] == target
return middle; // 数组中找到目标值,直接返回下标
}
}
// 未找到目标值
return -1;
}
};

27. 移除元素

暴力解(两层循环)

  • 自己写的错误解
    • 第二层循环的遍历范围有误
    • 手欠把多打了一个 = ,把赋值写成了判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for(int i = 0; i < size; i++) {
if(nums[i] == val) {
for(int j = i; j < size; j++) { // 错误1:j只需要遍历到size-1的位置,修改为: j < size-1
nums[j] == nums[j+1]; // 错误2:此处应该是=,进行赋值操作
}
size--;
i--;
}
}
return size;

}
};
  • 正确解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++) {
if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
for (int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
size--; // 此时数组的大小-1
}
}
return size;

}
};

双指针法

双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

力扣官方题解

由于题目要求删除数组中等于$val$ 的元素,因此输出数组的长度一定小于等于输入数组的长度,我们可以把输出的数组直接写在输入数组上。可以使用双指针:右指针 $right$ 指向当前将要处理的元素,左指针 $left$ 指向下一个将要赋值的位置。

如果右指针指向的元素不等于 $val$,它一定是输出数组的一个元素,我们就将右指针指向的元素复制到左指针位置,然后将左右指针同时右移;

如果右指针指向的元素等于 $val$,它不能在输出数组里,此时左指针不动,右指针右移一位。

整个过程保持不变的性质是:区间 $[0,left)$ 中的元素都不等于 $val$。当左右指针遍历完输入数组以后,left 的值就是输出数组的长度。

这样的算法在最坏情况下(输入数组中没有元素等 于$val$),左右指针各遍历了数组一次。

27.移除元素-双指针法

  • 自己写的错误解

    • 按照我的这种写法,慢指针就起不到对数组进行移动的效果,最后只是得到了数组里有几个目标值,得不到删除目标值后的数组
    • 正确解更新在下面的代码中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int slow = 0;
for (int fast = 0; fast < n; fast++) {
if(nums[fast] != val) {
// 添加 nums[slow] = nums[fast];
slow++;
}
}
return slow;

}
};

© 2024 Montee | Powered by Hexo | Theme stellar


Static Badge