day1 数组part01
数组理论基础
代码随想录-数组-1.数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合
优点:常数时间复杂度访问元素
缺点:在删除或者增添元素的时候,就难免要移动其他元素的地址,时间复杂度为O(n)
704. 二分查找
代码随想录-数组-2.二分查找
前提条件
二分查找前提条件:
- 数组为有序数组
- 数组元素无重复
满足以上两个条件的数组,查找元素时,一定要考虑二分查找
实现细节
溢出问题
计算中间索引的时候,要考虑防止溢出
错误的写法:int mid = (left + right) / 2
,left + right
有可能超出int
的范围
正确的写法:int mid = left + (right - left) / 2
确定边界条件
二分法最大的难点在于如何确定边界条件——根据查找区间的定义来做边界处理,要保持一致
原则:循环不变量规则(一致性)
- 先确定
left
和right
是左闭右开[left, right)
还是左闭右闭[left, right]
(left = 0
左闭右开:right = nums.size()
,左闭右闭:right = nums.size() - 1
) - 确定
while
循环条件(左闭右开:while (left < right)
,左闭右闭:while (left <= right)
) - 确定
left
和right
的更新方法
二分法有两种写法:
左闭右开
int search(vector<int>& nums, int target)
{
int left = 0, right = nums.size(); // 左闭右开
while (left < right) // 左闭右开while循环条件:当left == right时,说明区间内没有元素了
{
// int mid = (left + right) / 2; // 会溢出
int mid = left + (right - left) / 2; // 正确操作
if (nums[mid] < target) // target在mid的右侧,需要更新left
{
left = mid + 1; // 左闭
}
else if (nums[mid] > target) // target在mid的左侧,需要更新right
{
right = mid; // 右开
}
else
{
return mid;
}
}
return -1;
}
左闭右闭
int search(vector<int> &nums, int target)
{
int left = 0, right = nums.size() - 1; // 左闭右闭
while (left <= right) // 左闭右闭while循环条件:当left > right时,说明区间内没有元素了
{
int mid = left + (right - left) / 2;
if (nums[mid] < target) // target在mid右侧,需要更新left
{
left = mid + 1; // 左闭
}
else if (nums[mid] > target) // target在mid左侧,需要更新right
{
right = mid - 1; // 右闭
}
else
{
return mid;
}
}
return -1;
}
时间复杂度:O(logn)
空间复杂度:O(1)文章来源地址https://www.toymoban.com/news/detail-495454.html
27. 移除元素
代码随想录-数组-3.移除元素
使用双指针
实现细节
数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖
双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
定义快慢指针
- 快指针:遍历 旧数组,寻找新数组的元素 ,新数组就是不含有目标元素的数组
- 慢指针:指向更新 新数组下标的位置
代码实现
int removeElement(vector<int>& nums, int val)
{
int fast = 0, slow = 0;
while (fast < nums.size()) // 遍历数组
{
if (nums[fast] != val) // 寻找符合条件的元素,即不为val的元素
{
nums[slow] = nums[fast]; // 覆盖写入
++slow;
}
++fast;
}
return slow;
}
时间复杂度:O(n)文章来源:https://www.toymoban.com/news/detail-495454.html
空间复杂度:O(1)
到了这里,关于算法刷题Day1 二分查找+移除元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!