浏阳网站建设hnktwl,荆门网站建设公司,建设网站主机要买什么的好,seo搜索优化服务代码随想录二刷day01704. 二分查找27. 移除元素977. 有序数组的平方704. 二分查找
题目链接 做这种题最好现在纸上写一写#xff0c;如果在大脑中想#xff0c;可能一会就晕了。 二刷的时候发现了一个新的知识点 即#xff1a; 的作用 二分法第二种写法#xff1a…
代码随想录二刷day01704. 二分查找27. 移除元素977. 有序数组的平方704. 二分查找
题目链接 做这种题最好现在纸上写一写如果在大脑中想可能一会就晕了。 二刷的时候发现了一个新的知识点 即 的作用 二分法第二种写法左闭右开[left, right
left right 时没有意义if (nums[middle] target) right 要赋值为 middle 因为当前这个nums[middle]一定不是targetif (nums[middle] target) left 要赋值为 middle 因为当前这个nums[middle]一定不是target
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size(); // 定义target在左闭右开的区间里即[left, right)while (left right) { // 因为left right的时候在[left, right)是无效的空间所以使用 int middle left ((right - left) 1);if (nums[middle] target) {right middle; // target 在左区间在[left, middle)中} else if (nums[middle] target) {left middle 1; // target 在右区间在[middle 1, right)中} else { // nums[middle] targetreturn middle; // 数组中找到目标值直接返回下标}}// 未找到目标值return -1;}
};中 int middle left ((right - left) 1) 相当于 int middle left ((right - left) / 2) 举个小栗子
: 二进制右移
举个例子: 1010 1 0101
1010 十进制 10
0101 十进制 5
综上 1 作用相当于除二所以 left ((right -left) 1) left ((right -left)/2)
为什么不直接用(left right) /2 而用left ((right -left) 1) 答: 是因为left right 在某种情况下可能会超过基本类型所能容纳的最大值,而且 (位运算) 比 / 运算要快一点。
27. 移除元素
题目链接 解题思路 双指针(快慢指针法) 一快一慢。
本题中
快指针 是用来获取新数组中的元素慢指针是用来获取新数组中需要更新的位置。
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:int removeElement(vectorint nums, int val) {int slowIndex 0;for(int fastIndex 0; fastIndex nums.size();fastIndex){if(val ! nums[fastIndex]){nums[slowIndex] nums[fastIndex];}}return slowIndex;}
};注数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖。 977. 有序数组的平方
题目链接 注本题中给出的数组是有序的则最大值应该在两端不可能在中间。 采用双指针从两边向中间就行遍历并比较大小将大的放在右端。 i 指向 起始位置j指向终止位置
class Solution {
public:vectorint sortedSquares(vectorint nums) {int k nums.size() - 1;vectorint result(nums.size(),0);for(int i 0,j nums.size() - 1 ;i j ; ){if((nums[i] * nums[i]) (nums[j] * nums[j])){result[k--] nums[i] *nums[i];i;}else{result[k--] nums[j] * nums[j];j-- ;}}return result; //最终返回排序好的平方和数组}
};最终返回排序好的平方和数组。
