重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
代码随想录算法训练营第1天|数组1-创新互联
数组
网页题目：代码随想录算法训练营第1天|数组1-创新互联
路径分享：http://cqcxhl.com/article/dcdjje.html
数组是存放在连续内存空间上的相同类型数据的集合。
①数组的下标都是从0开始的
②数组内存空间的地址是连续的
因为数组在内存空间的地址是连续的，所以我们在删除或增添元素的时候，就需要移动其他元素的地址。
注：①vector是容器，array是数组，vector的底层实现是array。
②数组的元素是不能删除的，只能覆盖。
二维数组地址测试
#includeusing namespace std;
void Array2DAddress(){int array[2][3] = {{0, 1, 2},{3, 4, 5}};
cout<< &array[0][0]<< " "<< &array[0][1]<< " "<< &array[0][2]<< endl;
cout<< &array[1][0]<< " "<< &array[1][1]<< " "<< &array[1][2]<< endl;
}
int main() {Array2DAddress();
return 0;
}
输出：
0x16d537760 0x16d537764 0x16d537768
0x16d53776c 0x16d537770 0x16d537774注：int长度为4个字节，根据输出结果可知，二维数组的数据存储方式仍然是连续的。
704.二分查找题目： 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
链接： https://leetcode.cn/problems/binary-search
思路： 二分查找的循环不变量规则，在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作。
二分法区间定义： 左闭右闭[left, right]和左闭右开[left, right)
- 左闭右闭
[left, right]写法
定义目标值target在一个左闭右闭[left, right]的区间里：
①while(left<= right)要使用<=因为left == right是有意义的；
②if(nums[middle] >target)right = middle - 1，因为此时的nums[middle]一定不等于target；
③if(nums[middle]< target)left = middle + 1，因为此时的nums[middle]一定不等于target；
class Solution {public:
int search(vector& nums, int target) {int left = 0;
int right = nums.size() - 1;
while(left<= right){ //int middle = (left + right) / 2;
int middle = left + (right - left) / 2;
if(nums[middle] >target){ right = middle - 1;
}
else if(nums[middle]< target){ left = middle + 1;
}
else{ return middle;
}
}
return -1;
}
}; - 左闭右开
[left, right)写法
定义目标值target在一个左闭右开[left, right）的区间里：
注：right = nums.size()来保证target在题目给出的区间内能遍历到最后一个元素。
①while(left< right)要使用<因为left == right是没有意义的；
②if(nums[middle] >target)right = middle，因为此时的nums[middle]有可能等于target；
③if(nums[middle]< target)left = middle + 1，因为此时的nums[middle]一定不等于target；
class Solution {public:
int search(vector& nums, int target) {int left = 0;
int right = nums.size();
while(left< right){ //int middle = (left + right) / 2;
int middle = left + (right - left) / 2;
if(nums[middle] >target){ right = middle;
}
else if(nums[middle]< target){ left = middle + 1;
}
else{ return middle;
}
}
return -1;
}
}; 总结： 二分法在使用的过程中最重要的是弄清楚区间的定义，在循环中始终坚持根据查找区间的定义来做边界处理。
35.搜索插入位置题目： 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
链接： https://leetcode.cn/problems/search-insert-position
思路： 二分查找，若数组中存在目标值则为普通的二分查找，若数组中不存在目标值，则插入位置应该在while循环跳出时left的位置。
class Solution {public:
int search(vector& nums, int target) {int left = 0;
int right = nums.size() - 1;
while(left<= right){ //int middle = (left + right) / 2;
int middle = left + (right - left) / 2;
if(nums[middle] >target){ right = middle - 1;
}
else if(nums[middle]< target){ left = middle + 1;
}
else{ return middle;
}
}
return left;
}
}; 题目： 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
链接： https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
思路： 寻找target在数组的左右边界，有三种可能的情况：
①target在数组范围之外，也就是大于大的小于最小的。例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回[-1,-1]。
②target在数组范围之内，但数组中不存在target。例如数组{3, 4, 7}，target为5，此时应该返回[-1,-1]。
③target在数组范围之内，但数组中存在target。例如数组{3, 6, 7}，target为6，此时应该返回[1, 1]。
- 二分查找，首先两次二分查找分别找到左边界
leftIdx和右边界rightIdx，校验[left, right]是否满足条件，不满足则返回[-1,-1]。 - 二分查找左边界
leftIdx。
int searchLeftIdx(vector& nums, int target) {int left = 0;
int right = nums.size() - 1;
int leftIdx = -1;
while(left<= right){//int middle = (left + right) / 2;
int middle = left + (right - left) / 2;
if(nums[middle]<= target){right = middle - 1;
leftIdx = right;
}
else{left = middle + 1;
}
}
return leftIdx;
} - 二分查找右边界
rightIdx。
注：此右边界rightIdx是第一个大于target的元素的位置。
int searchRightIdx(vector& nums, int target) {int left = 0;
int right = nums.size() - 1;
int rightIdx = -1;
while(left<= right){//int middle = (left + right) / 2;
int middle = left + (right - left) / 2;
if(nums[middle] >target){right = middle - 1;
}
else{left = middle + 1;
rightIdx = left;
}
}
return rightIdx;
} - 检验+约束
vectorsearchRange(vector& nums, int target) {int leftIdx = searchLeftIdx(nums, target) + 1;
int rightIdx = searchRightIdx(nums, target) - 1;
if(leftIdx<= rightIdx && nums[leftIdx] == target && nums[rightIdx] == target){return vector{leftIdx, rightIdx};
}
return vector{-1, -1};
} 题目： 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
链接： https://leetcode.cn/problems/remove-element
注意： 数组元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
思路：
- 暴力解法
两层for循环，一层for循环遍历数组元素，一层for循环更新数组。
class Solution {public:
int removeElement(vector& 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--;
size--;
}
}
return size;
}
}; 时间复杂度：O(N^2)
空间复杂度：O(1)
2. 双指针法
通过一个快指针和慢指针在一层for循环下完成两个for循环的工作。
快指针：寻找新数组的元素，新数组就是不包含目标元素的数组
慢指针：指向更新新数组下标的位置。
class Solution {public:
int removeElement(vector& nums, int val) {int slowPointer = 0;
for(int fastPointer = 0; fastPointer< nums.size(); ++fastPointer){ if(nums[fastPointer] != val){ nums[slowPointer] = nums[fastPointer];
slowPointer++;
}
}
return slowPointer;
}
}; 时间复杂度：O(N)
空间复杂度：O(1)
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页题目：代码随想录算法训练营第1天|数组1-创新互联
路径分享：http://cqcxhl.com/article/dcdjje.html