侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第一天 | 704. 二分查找、27. 移除元素。

thinkTV
2023-04-19 / 0 评论 / 2 点赞 / 2,193 阅读 / 1,115 字 / 正在检测是否收录...

1. 数组理论基础

代码随想录 原文

数组是存放在连续内存空间上的相同类型数据的集合。

需要两点注意的是

  • 数组下标都是从0开始的。
  • 数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就需要移动其他元素的地址。

数组的元素是不能删的,只能覆盖。(暴力法遍历)

2. 二分查找

代码随想录 原文

力扣题目: 704. 二分查找

2.1 思路

二分查找满足条件:

  • 数组为有序数组
  • 数组中无重复元素

二分查找关键问题:

  • 二分法的边界条件
  • 更新区间的边界条件

2.2 左闭右闭的区间定义

定义 target 是在一个在左闭右闭的区间里,也就是[left, right]

  • while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]
        while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间,所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间,所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

2.3 左闭右开的区间定义

定义 target 是在一个在左闭右开的区间里,[left, right)

  • while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]
// 版本二
class Solution {
public:
    int search(vector<int>& 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] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

3. 移除元素

代码随想录 原文

力扣题目: 27. 移除元素

3.1 思路

注意:数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖

3.2 暴力解法

两层for循环,一个for循环遍历数组元素 ,第二个for循环更新数组。

// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

3.3 双指针法

通过一个快指针慢指针在一个for循环下完成两个for循环的工作。

  • 快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
  • 慢指针:指向更新 新数组下标的位置
// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

4. 总结

  • 理清了二分查找的边界条件
  • 扩展了双指针法思路
  • 学习耗时110分钟
2

评论区