沈阳 建设工程 招标中心网站,《企业宣传片制作》,wordpress如何屏蔽特定国家的用户,做网站做生意Leetcode 704 二分查找题目链接#xff1a;704二分查找介绍给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。思路先看看一个…Leetcode 704 二分查找题目链接704二分查找介绍给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。思路先看看一个动画可以看出二分查找只用了3次即可查找成功而顺序查找却要用12次。二分查找算法的原理如下 1. 设置查找区间low 0high n 2. 若查找区间[low, high]不存在则查找失败否则转步骤3 3. 取中间位mid (low high) / 2比较 target 与 arr[mid]有以下三种情况 3.1 若 target arr[mid]则high mid - 1查找在左半区间进行转步骤2 3.2 若 target arr[mid]则low mid 1查找在右半区间进行转步骤2 3.3 若 target arr[mid]则查找成功返回 mid 值二分法易错点边界问题—一般情况下写二分法时要么是左闭右闭要么是左闭右开区间不一样时会影响边界条件的处理。while(leftright) 还是while(leftright)if(targetnums[middle]) right mid 还是right mid -1左闭右闭left 0
right num.size-1
while(leftright){ //[1,1]时leftright是合法区间middle (leftright)/2if(target nums[middle]) right middle - 1;else if(target nums[middle]) left middle 1;else return middle;
}
return -1
}左闭右开left 0
right num.size
while(leftright){ //[1,1)开不包含右边界闭包含左边界这里又包含又不包含说明不是一个合 法的区间middle (leftright)/2if(target nums[middle]) right middle;else if(target nums[middle]) left middle 1;else return middle;
}
return -1
}代码class Solution {
public:int search(vectorint 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(target nums[middle]){right middle - 1;}else if(target nums[middle]){left middle 1;}else{return middle;}}return -1;}
};Leetcode 27 移除元素题目链接27 移除元素介绍给你一个数组 nums 和一个值 val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。思路数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖。即在数组中如果要删除x那么就得让x后面的元素一个个覆盖到前一个上去。c中的vector或java/python会提供数组的接口删除元素后返回的数组size会-1但并不代表实际空间-1。例如vector.erase可以删除数组中的某一个元素实际上这个函数也是进行了一个覆盖的操作时间复杂度为O(n)。思路一暴力实现两层for循环第一层for循环遍历数组找到要删除的元素第二层for循环将要删除元素后面的元素覆盖到前面来。思路二双指针思路O(n)使用一层for循环做了两层for循环所做的事。定义一个快指针fastIndex获取新数组中的元素定义一个慢指针slowIndex指向更新新数组下标的位置开始的时候fastIndex移动直到找到所要删除的元素后给慢指针slowIndex赋值。将fastIndex指向后一个元素方便覆盖然后将nums[fastIndex]的值赋给nums[slowIndex]再将fastIndex,slowIndex。slow 0;
for(fast0;fastnums.size;fast){if(nums[fast]val){nums[slow] nums[fast];//把快指针指向的值赋给慢指针所在的位置slow //慢指针}//如果nums[fast]val就只需要让fast就行也就是继续进行for循环中的fast操作//最后slow所指向的下标的位置就是新数组的大小
}
return slow;代码class Solution {
public:int removeElement(vectorint nums, int val) {int slowIndex 0;int fastIndex;for(fastIndex0;fastIndexnums.size();fastIndex){if(nums[fastIndex]!val){nums[slowIndex] nums[fastIndex];}}return slowIndex;}
};
