代码编织梦想


一、数组基础知识

数组是存放在连续内存空间上的相同类型数据的集合。可以方便的通过下标索引的方式获取到对应的数据。

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

正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。例如删除下标为3的元素,需要对下标为3的元素后面的所有元素都要做移动操作

C++中要注意vector 和 array的区别,vector的底层实现是array,严格来讲vector是容器,不是数组。
数组的元素是不能删的,只能覆盖。

二、二维数组

二维数组在内存的空间地址是连续的吗?在C++中二维数组是连续分布的。

void test_arr() {
    int array[2][3] = {
		{0, 1, 2},
		{3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}

输出结果:

0x7ffee4065820 0x7ffee4065824 0x7ffee4065828
0x7ffee406582c 0x7ffee4065830 0x7ffee4065834

地址为16进制
0x7ffee4065820 与 0x7ffee4065824 差了一个4,就是4个字节,因为这是一个int型的数组,所以两个相邻数组元素地址差4个字节。

0x7ffee4065828 与 0x7ffee406582c 也是差了4个字节,在16进制里8 + 4 = c,c就是12。

704 二分查找

二分法使用条件:分析题干可知,数组升序、且无重复元素时才可以使用。(有重复元素时使用二分法返回的元素下标可能不唯一)

1.左闭右闭

left <= right

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; // 数组中找到目标值,直接返回下标
            }

if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1

2.左闭右开

left < right

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; // 数组中找到目标值,直接返回下标
            }

while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的。
if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]

细节:int middle = left + ((right - left) >> 1);
或者用int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2

27 移除元素

1.双指针法(快慢指针法):
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

2.定义快慢指针
快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
慢指针:指向更新 新数组下标的位置

// 时间复杂度: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;
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_54479347/article/details/126982237

数据结构KMP算法配图详解(超详细)-爱代码爱编程

KMP算法配图详解 前言 KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂,很多正规的书本把概念一摆出直接劝退无数人。这篇文章将尽量以最详细的方式配图介绍KMP算法及其改进。文章的开始我先对KM

数据结构与算法二:数组-爱代码爱编程

一维数组: 一、概述: 数组在内存中是一片连续的空间且元素相同可以快速根据索引定位到某元素但是新增、删除元素的时候需要移动元素位置,效率会变低二、数组的声明与创建: 1.有两种声明方式:int[] a; int a[]; 2.创建方式有两种: int[] a1 = new int[5]; //直接指定大小 int[] a2 ={1,2}; //有

数据结构学习思考:KMP算法求解next数组-爱代码爱编程

这是2022版王道书数据结构第110页上的KMP算法求解next数组算法,书中没有详细说明原理,且咸鱼学长也说这是整个课程中比较晦涩的算法之一,引发了笔者的思考。   void get_next(String T,int next[]){ int i=1, j=0; next[1]=0; while(i<T.length)

二、数据结构与算法 稀疏数组-爱代码爱编程

1.稀疏算法的目的就是储存的时候,不用储存那么多,节省空间(时间换空间)。 稀疏数组:就是无效值(可以是规定值吧,相同的比较多)比较多,很稀疏,其实就是把原来的数组(这个数组有多个相同的值,这里是0,因为默认值为0,无值的情况默认0,不用设置值,而其他的值要设置值),通过规律来创建一个新的数组(值较少,且可以按一定规律还原为原数组),然后储存起来,然后。