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

小明 2025-05-08 00:26:13 7

数组第一天

基础知识

  1. ���组是存放在连续内存空间的一系列数据

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

    （）

    b. 数组可以通过下标索引的方式获取下表对应的数据（数组可以根据数组下标很好的读取）

    ① 数组的下标从0开始

    （）

    ② 数组内存空间的地址是连续的

    c. 因为数组在内存空间的地址是连续的，因此数组的增删，需要移动其他数据的地址

    d. 数组的元素无法删除，只能覆盖

  2. C++中，vector和array是不一样的，vector的底层实现是数组array，严格来讲vector是一个封装好的容器，而不是数组
  3. 二维数组在内存的空间地址是连续嘛？不同编程语言的内存管理是不一样的内存存储在不同语言中是不一样的，

    a. 在C++中的二位数组是连续分布的（int类型的内存4个字节）

    [图片]

    b. 但是在Java中可能是不连续的，因为Java没有指针，同时也不会对程序员暴露其元素的地址，寻址操作完全交给虚拟机，看不到每个元素的地址情况，Java的二维数组可能排列情况：

    [图片]

    数组（Array）：

  • 静态大小：数组的大小在编译时就确定了，一旦定义就不能更改。
  • 堆栈分配：通常数组在栈上分配，这意味着它的生命周期由其所在的作用域管理。
  • 内存利用：不像 vector，数组不会自动处理内存的分配和释放。
  • 性能：直接访问数组元素通常比 vector 快，因为没有额外的内存管理开销。 
    int myArray[3];        // 静态数组，大小为3
myArray[0] = 10;
myArray[1] = 20;
myArray[2] = 30;
for (int i = 0; i  

    向量（Vector）：
    • 动态大小：vector 的大小可以在运行时动态改变。
    • 堆分配：vector 通常在堆上分配内存，可以动态增长。
    • 内存管理：vector 会自动处理内存的分配和释放。
    • 功能丰富：vector 提供了很多辅助函数，比如 push_back(), pop_back(), insert(), erase() 等。 
      std::vector myVector;  // 动态向量
myVector.push_back(10);
myVector.push_back(20);
myVector.push_back(30);
for (int i = 0; i  

      Vector 和 array 区别与联系：
      • 动态性：数组是静态的，一旦创建，大小不变。vector 是动态的，可以根据需要增加和减少大小。
      • 内存管理：数组没有内置的内存管理，而 vector 会自动管理内存。
      • 接口：vector 提供了一组丰富的成员函数来管理元素，数组则没有。
      • 性能：对于性能敏感的应用，数组可能会稍微快一些，因为 vector 在动态调整大小时可能会产生额外开销。

        尽管数组和 vector 有上述区别，但它们也有联系。从概念上讲，它们都是元素的有序集合，并提供通过索引访问元素的能力。此外，vector 内部实际上是使用数组来存储元素的，因此它们的数据存储方式是连续的。在需要固定大小的序列数据且对性能要求较高时可以选择数组，而当需要灵活的、可以动态调整大小的容器时，则更适合使用 vector。

        题目

        从704. 二分查找

        自己的代码（过了）【应该是左闭右闭的区间，还有左闭右开的】

        回忆了很久，确实很久没写代码了，记得本科的时候做的唯一一道面试题也是这个，当时> target 时，说明，target如果存在也是存在数组mid往左，又因为nums[mid]已经判断过了,这时在[left，mid-1]中寻找，所以使得right更新为 mid -1

      • 同理可得 当nums[mid]

        接着就是循环条件跳出的判定，二分查找的条件是查找范围不为空，即 left≤right。如果 target在数组中，二分查找可以保证找到 target，返回 target 在数组中的下标。如果 target 不在数组中，则当 left>right时结束查找，返回 −

        复杂度分析

      • 时间复杂度：O(log⁡n)O(\log n)O(logn)，其中 nnn 是数组的长度。
      • 空间复杂度：O(1)O(1)O(1)。

        复盘分析

      • mid = (right - left) / 2 + left 和 mid = (mid + right) / 2 区别
        • mid = (mid + right) / 2可能会超出两数相加范围，导致溢出问题
        • 同时需要注意二分法的适用范围
          • 有序数组
          • 数组中无重复数组（否则返回的元素下表可能不是唯一）
          • 循环不变量：

            循环不变量是用于设计和分析循环的一种强大技术，特别是在证明算法的正确性方面。循环不变量是一个在循环的每次迭代之前和之后都保持为真的条件或性质。它帮助我们理解循环的行为，并证明循环结束时算法的正确性。要证明一个循环正确，通常需要证明三点：

            1. 初始化：在循环开始前，不变量已经成立。
            2. 保持：如果不变量在循环的某次迭代之前是成立的，那么在这次迭代之后它仍然成立。
            3. 终止：在循环终止时，不变量提供了一个有用的性质，这个性质帮助证明算法的正确性。
            class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        if (nums[0] > target || nums[right]  target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
};

            到27. 移除元素

            解题的时候没想那么多，直接就按照数学思想进行，其实也可以归类为双指针法，但是没那么明显。

            双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。我不同的地方在于设置一个中间值判断删减的个数，然后通过每次的相减判断慢指针的位置。

            class Solution {
public:
    int removeElement(vector& nums, int val) {
        int delnum = 0;
        int n = nums.size();
        if(n==0)
            return 0;
        for(int temp = 0;temp
The End

标签：

微信