可信赖的做pc端网站,网站设计模板安全吗,wordpress文档id初始化,品牌推广的具体方法二分查找 力扣704
贴一下之前的笔记#xff1a; 没想到一下子写不出来#xff0c;忘记什么是二分法了#xff0c;这里回顾一下#xff1a;
「二分查找 binary search」是一种基于分治策略的高效搜索算法。
它利用数据的有序性#xff0c;每轮减少一半搜索范围#xff…二分查找 力扣704
贴一下之前的笔记 没想到一下子写不出来忘记什么是二分法了这里回顾一下
「二分查找 binary search」是一种基于分治策略的高效搜索算法。
它利用数据的有序性每轮减少一半搜索范围直至找到目标元素或搜索区间为空为止。
注意前提是①有序②不重复③连续空间④较大量数据 整体思想就是控制搜索的范围先是[left, right)然后[left, mid)[mid, right) 需要去根据mid的值与target的大小关系来确定下一步的搜索区间。
时间复杂度是logN 空间复杂度是1
小数据量下线性查找性能更佳。在线性查找中每轮只需要 1 次判断操作而在二分查找中需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法减法共 4 ~ 6 个单元操作因此当数据量 较小时线性查找反而比二分查找更快。
class Solution {
public:int search(vectorint nums, int target) {int left 0, right nums.size();while(leftright){int middle left (right - left)/2;if(nums[middle]target){right middle;}else if(nums[middle]target){left middle1;}else{return middle;}}return -1;}
};补充
另一种写法也是我准备以后沿用的方法
int BinarySearch(vectorint v, int target)
{int i 0, j v.size() - 1;while (i j){int mid i (j - i) / 2;if (v[mid] target){i mid 1;}else if (v[mid] target){j mid - 1;}else {return mid;}}return -1;
}此方法关键点
while的条件为什么是i≤j而不是ij
想清楚因为i≤j依旧可以从i到j中找到一个数
为什么是i mid 1而不是 i mid
要明确i到j的区间究竟是什么
是target可能的值的区间所以不要把不可能是target的数字包含进来
移除元素 力扣27
这道很简单使用双指针即可
class Solution {
public:int removeElement(vectorint nums, int val) {int slow 0;for(int i 0; i nums.size();i){if(nums[i]!val){nums[slow] nums[i];}}return slow;}
};class Solution {
public:int removeElement(vectorint nums, int val) {int slow 0, fast 0;for (; fast nums.size();){if (nums[fast] val){fast;}else {nums[slow] nums[fast];}}nums.resize(slow);return nums.size();
}
};相关题 移动零 https://leetcode.cn/problems/move-zeroes/
v1.0:用快指针搜索所有不为0的项再用0补满
class Solution {
public:void moveZeroes(vectorint nums) {int slow 0;for(int i 0; inums.size();i){if(nums[i]!0){nums[slow] nums[i];}}for(;slownums.size();slow){nums[slow] 0;}}
};删除排序数组中的重复项 https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
class Solution {
public:int removeDuplicates(vectorint nums) {if(nums.size()1)return 1;int slow 0;for(int i 0; inums.size()-1;i){if(nums[i]!nums[i1]){nums[slow] nums[i];if(inums.size()-2){nums[slow] nums[nums.size()-1];}}else{if(inums.size()-2){nums[slow] nums[nums.size()-1];}}}return slow;}
};上班真累啊还好这两道题之前都写过 温故知新
