二分查找 力扣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(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while(left<right){
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;
}
};
补充:
另一种写法,也是我准备以后沿用的方法:
int BinarySearch(vector<int> 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而不是i<j
想清楚,因为i≤j依旧可以从i到j中找到一个数
为什么是i = mid + 1而不是 i= mid?
要明确i到j的区间究竟是什么?
是target可能的值的区间,所以不要把不可能是target的数字包含进来
移除元素 力扣27
这道很简单,使用双指针即可
class Solution {
public:
int removeElement(vector<int>& 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(vector<int>& 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(vector<int>& nums) {
int slow = 0;
for(int i = 0; i<nums.size();i++){
if(nums[i]!=0){
nums[slow++] = nums[i];
}
}
for(;slow<nums.size();slow++){
nums[slow] = 0;
}
}
};
删除排序数组中的重复项 https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()==1)return 1;
int slow = 0;
for(int i = 0; i<nums.size()-1;i++){
if(nums[i]!=nums[i+1]){
nums[slow++] = nums[i];
if(i==nums.size()-2){
nums[slow++] = nums[nums.size()-1];
}
}
else{
if(i==nums.size()-2){
nums[slow++] = nums[nums.size()-1];
}
}
}
return slow;
}
};
上班真累啊,还好这两道题之前都写过 ,温故知新