704 二分查找
数组基础
数组空间地址连续、随机访问时间复杂度O(1）、删除和移动时间复杂度O(n)
vector和array区别：vector底层实现为array；array是栈上开辟空间、vector是堆上开辟空间；array不支持迭代器访问，支持指针和索引、vector还支持迭代器访问
二分查找适用场景
有序数组、数组内元素不重复
二分查找原理
区间不断二分，减少查找次数
根据区间划分为左闭右开或者左闭右闭，实现细则上有差异
code易错点
- while(l <= r) 是否取等：有开区间不取等
- l和r 边界变化：看选取区间是否包含
左闭右开实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size();
int mid;
while (l < r) {
mid = (l + r) >> 1; //如果考虑越界，可改为mid = l + (r - l) >> 1;
if (nums[mid] == target) {
return mid;
} else if ( nums[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}
return -1;
}
};
左闭右闭实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
int mid;
while (l <= r) {
mid = (l + r) >> 1;
if (nums[mid] == target) {
return mid;
} else if ( nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
};
27 删除元素：erase的实现
数组的删除其实是覆盖
数组的内存一旦开辟，不能只删除其中一个元素，所谓的删除其实是后面的元素覆盖前面的元素：erase的原理
库函数的使用须知：底层实现以及时间复杂度
erase：底层实现是后面的元素移动到前面进行覆盖
size():尽管在调用一个erase函数后返回值变化，但实际只是c++做的封装，实际内存依然是刚开始开辟的内存
erase的实现
暴力遍历：两层循环，一层检查元素，一层移动覆盖
快慢指针：快指针先前获取目标元素的索引，慢指针为目标元素存储的位置
暴力遍历实现
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++) { // i < nums.size()会超时
if (nums[i] == val) {
size--;
for (int j = i + 1; j < nums.size(); j++) {
nums[j - 1] = nums[j];
}
i--; //注意移动
}
}
return size;
}
};
快慢指针实现
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
int slow = 0;
for (int fast = 0; fast < size; fast++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow; //注意返回是慢指针索引
}
};