数组 PART 1
704. 二分查找
leetcode.704 题目链接
二分查找文字讲解
二分查找视频讲解
解题思路： 首先要确认包含数据的区间的类型(闭区间，闭开区间)，并将这个区间类型作为循环不变量，因为寻找的数字一定包含在这个区间内是不变的，以这个区间类型合法区间作为边界条件就不会出错。并且在计算middle的时候有一个注意事项是当两个整数相加的时候为了防止溢出可以采用 left + (right - left)/ 2 或者 left + ((right - left) >> 1)的形式。
二分查找适用的题目类型：有序数组且无重复元素
时间复杂度：O(logn)
空间复杂度：O(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
25
26
27
28
29
30
| #include<iostrem>
#include<vector>
using namespace std;
int main(){
vector<int> nums = {-1,0,3,5,9,12};
int target = 9;
int left = 0;
int right = nums.size()-1;
while(left <= right){
int middle = left + (right - left)/2;
if(nums[middle] < target){
left = middle + 1;
}else if(nums[middle] > target){
right = middle - 1;
}else{
count << middle << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
|
合法区间为开闭区间的代码实现：
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
| #include<iostream>
#include<vector>
using namespace std;
int main(){
vector<int> nums = {-1,0,3,5,9,12};
int target = 2;
int left = 0;
int right = nums.size();
while(left < right){
int middle = left + ((right - left) >> 1);
if(nums[middle] < target){
left = middle + 1;
}else if(nums[middle] > target){
right = middle;
}else{
cout << middle << endl;
return 0;
}
}
cout << middle << endl;
return 0;
}
|
27. 移除元素
leetcode.27 题目链接
移除元素文字讲解
移除元素视频讲解
解题思路：
首先需要注意的点是数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。 移除元素只是元素在数组长度中不可见了，但实际的数组内存大小并没有发生改变，vector的erase方法等是在数组的基础上进行了进一步封装提供的接口，隐藏了这一过程。
移除数组主要有两种方式，一种是暴力移除，需要用到两个for循环，一个for循环用来寻找移除元素的位置，另一个for循环用来将这个位置后续的元素向前移动覆盖掉需要移除的元素。时间复杂度为O($n^2$)。暴力移除有两个需要注意的点，一个是作为第一层for循环的边界数组大小size是动态改变的，另一个是在执行完覆盖操作后要加指向删除指针的位置后退一步防止漏查需要删除的元素。
另一种更为推荐的方式是通过双指针操作。定义两个指针，快指针和慢指针，快指针寻找新数组的元素，新数组指的就是不含有移除元素的数组，慢指针指向新数组更新的下标位置。逻辑上慢指针就相当于暴力解法的第一层循环，找到要移除元素的位置，快指针寻找移除这个元素后这个位置需要覆盖的元素，因为用来覆盖的元素一定在移除位置后第一个非移除元素的位置，所以指针向前移动不需要像暴力移除一样做回溯。利用寻找新数组的元素的思想来实现这个逻辑可以简化代码。
时间复杂度：
空间复杂度：
暴力解法的版本：
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
| #include<iostream>
#include<vector>
using namespace std;
int main() {
vector<int> nums = { 0, 1, 2, 2, 3, 0, 4, 2 };
int val = 2;
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--;
size--;
}
}
cout << size << endl;
return 0;
}
|
通过双指针的解法（推荐）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<iostream>
#include<vector>
using namespace std;
int main() {
vector<int> nums = { 0,1,2,2,3,0,4,2 };
int val = 2;
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (nums[fastIndex] != val) {
nums[slowIndex++] = nums[fastIndex];
}
}
cout << slowIndex << endl;
return 0;
}
|
977. 有序数组的平方
leetcode.977 题目链接
有序数组的平方文字讲解
有序数组的平方视频讲解
解题思路： 同样分为暴力解法和双指针解法。暴力解法思路比较直接，直接把数组元素平方之后做快排，算法的时间复杂度取决于排序算法的时间复杂度。双指针解法和上一个略有不同，这次并不是同向移动而是左右向的对撞移动。因为给定的数组是按非降序排列，平方后的最大值一定出现在两端，所以通过两个指针比较两端元素的大小，并从两端向中间推进，就是在从大到小的寻找平方后新数组的元素。因为题目要求的顺序是从小到大非降序排序，所以对新数组的赋值从后向前进行。
需要注意的是新数组的构建，我第一次构建数组的时候用vector<int> results = {}, 当
k = nums.size() - 1 的时候给results[k]赋值出现越界错误，用vector<int> results(nums.size(), 0) 构建就不会出现问题了。
trick:
sort(start_iterator, end_iterator) is included in "algorithm"vector<int> results(nums.size(), 0);
暴力解法版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
vector<int> nums = { -4, -1, 0, 3, 10 };
for (int i = 0; i < nums.size(); i++) {
nums[i] *= nums[i];
}
sort(nums.begin(), nums.end());
return 0;
}
|
双指针解法版本：
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
| #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
vector<int> nums = { -4, -1, 0, 3, 10 };
vector<int> results(nums.size(), 0);
int k = nums.size() - 1;
int i = 0;
int j = nums.size() - 1;
while (i <= j) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
results[k--] = nums[i] * nums[i];
i++;
}
else {
results[k--] = nums[j] * nums[j];
j--;
}
}
return 0;
}
|
