数组基础理论
1.数组的基本特征
1）下标从0开始
2）连续数组内存空间地址是连续的
3）数组元素不能删除，只能覆盖（也就是说，如果要删除数组内的一个元素，需要把之后的所有元素依次挪动）
2.C++中的数组实现
C++中数组实现包括vector和array。
1）vector
vector属于STL容器，不是数组，其迭代器包括：first、last和end。
扩容方式包括：固定扩容（空间利用率高但是时间复杂度高）和加倍扩容（空间利用率低但是时间复杂度低）。实际应用通常用空间换时间。
vector的部分函数：
2）array
vector的底层实现是array。
704二分查找
思考过程：
分而治之的方法，不断迭代，直到只剩一个元素，进行判断。。
但是这好像效率并没有提高，和遍历检测相比，是不是不断循环调用耗费的时间更多？
好了，有这个思路想试试也写不出来，代码能力太差了，看解析去了
看解答：
我忽视了数组是有序排列这个必要条件了，这样就只需要比较和中间值的大小就可以确定是哪个区间了。之前想的思路是递归不是二分emmm
试着按照这个思路写下，我觉得二分的难点主要是边界值的确定上
自己试写一版：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = size(nums);
int mid;
while(left <= right){
mid = (right - left) / 2;
if(target == nums[mid]) return mid;
else if(target < nums[mid]){
right = mid;
}
else if(target > nums[mid]){
left = mid;
}
}
return -1;
}
};
错误：超出时间限制
为啥呢？是不是while没跑出来？
突然发现我的right最开始设置的size，虽然对后面没什么影响，但是要注意最后的标号是size-1
发现我的mid赋值在while里面！！！这样mid一直是一样的达不到二分的效果，肯定跑不出循环
修改了还是超时
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
int mid = (right - left) / 2;;
while(left <= right){
if(target == nums[mid]) return mid;
else if(target < nums[mid]){
right = mid - 1;
mid = (right - left) / 2;
}
else if(target > nums[mid]){
left = mid + 1;
mid = (right - left) / 2;
}
}
return -1;
}
};
思考了一下之前的left和right是一直变的，倒是也可以，反而是现在的代码麻烦了
好的看了答案，没有把mid的值设置对
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left <= right){
int mid = left + (right - left) / 2;
if(target == nums[mid]) return mid;
else if(target < nums[mid]){
right = mid - 1;
}
else if(target > nums[mid]){
left = mid + 1;
}
}
return -1;
}
};
可以通过
总结：
1.注意题目中给定数据是不是有序的
2.注意左右区间的取值，判断的范围
3.注意中值的赋值
27.移除元素
思考过程：
题目中给定的数据是无序的，用二分法不合适（所以是不是能推断出二分法仅仅适用于有序数组？）
查找和删除移动元素很简单，用for就可以实现，题目中规定了O（1）的额外空间不知道超不超，试试
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int time=0;
for(int i = 0;i < nums.size(); i++){
if (nums[i] == val){
time = time + 1;
for(int j = i; j < nums.size() - 1; j++){
nums[j] = nums[j + 1];
}
}
}
return time;
}
};
解答错误，从输出来看，应该是边界出了问题
仔细一看确实，没有覆盖掉，可是最后一个怎么删除呢？数组不是不能删除吗？
看代码随想录
还是出现了边界值的问题，没有考虑覆盖后的边界值变化和数组大小的变化
改变后
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int time=0;
int size=nums.size();
int i ;
for(i = 0;i < size; i++){
if (nums[i] == val){
time = time + 1;
for(int j = i; j < size - 1; j++){
nums[j] = nums[j + 1];
}
}
}
size--;
i--;
return time;
}
};
还是有边界值的问题，卡哥代码写的j-1开始，是不太像这里的问题，但是试试
果然不是这里的问题
是位置的问题，并且我把题目看错了....
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int time=0;
int size=nums.size();
int i ;
for(i = 0;i < size; i++){
if (nums[i] == val){
time = time + 1;
for(int j = i+1; j < size; j++){
nums[j-1] = nums[j ];
}
size--;
i--;
}
}
return size;
}
};
暴力居然AC了.....
（啊~~~~刚刚笔试完，感觉前面思考的都忘了）
双指针没有学过，直接看代码随想录
双指针：一个快指针一个慢指针，用一个for循环实现两个for循环的工作；
当快指针检测到目标值时，只有快指针向前运动，慢指针不动；
当没有检测到目标值时，快指针慢指针都向前运动。如果两个指针指向不同，快指针的值覆盖慢指针指向的位置。
看了卡哥代码之后我思考好像复杂了，不需要判断两个指针是不是指向不一样，强制覆盖就可以。
这道题实际上是用指针的思想，并没有真正的使用指针，看到双指针名字的时候差点被劝退~~~
让我把这个思想复现一下
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
int fastIndex ;
for(fastIndex = 0;fastIndex < nums.size(); fastIndex++){
if(nums[fastIndex] == val){
nums[slowIndex] = nums[fastIndex];
slowIndex ++;
}
}
return slowIndex;
}
};
居然报错了，看看是哪里和卡哥不一样
整个思路没有错，居然是判断正好写反了！！他的测试用例刚好是四个，两个相同两个不同就通过了...
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
int fastIndex ;
for(fastIndex = 0;fastIndex < nums.size(); fastIndex++){
if(nums[fastIndex] != val){
nums[slowIndex] = nums[fastIndex];
slowIndex ++;
}
}
return slowIndex;
}
};
AC啦！！
总结：
1.认真读题！！
2.注意判断条件有没有写反！
3.双指针并不是真的使用了两个指针，是使用指针指向的思想，将两个for循环节省为一个for循环
4.感觉双指针用起来很灵活，适合数组“删除“类题目，其他题目做到之后再补充。
好啦我要开始大总结啦
今天是刷代码随想录第一天，中间有笔试和各种事情，没有具体统计时长，但是感觉是超了4小时的。
我的代码实现能力真的太差了！！中间出了奇奇怪怪的问题，比如赋值没赋对，没考虑边界，判断条件写反！多练一练复现！
啊对还有我的读题能力emmmm
拿到题不用着急做，先把题读明白，思路捋清楚做题更快~
明天见~~
