数组深入学习感悟

2023-12-21 00:42:34

注：本文学习借鉴于《代码随想录》

一.介绍数组

数组是储存在连续内存空间中的相同类型数据的集合

数组名的理解：

数组名就是数组?元素(第?个元素)的地址是对的，但是有两个例外：
sizeof(数组名)，sizeof中单独放数组名，这?的数组名表?整个数组，计算的是整个数组的??，
单位是字节
&数组名，这?的数组名表?整个数组，取出的是整个数组的地址（整个数组的地址和数组?元素
的地址是有区别的）
除此之外，任何地?使?数组名，数组名都表??元素的地址
数组中的元素不能删除，只能覆盖。

二.数组解题法

下面我们介绍数组解决问题的几大方法。

1.二分查找

适用类型：对于数组中在范围查找元素的位置，求解平方根，以及插入元素等。

使用前提：二分查找使用前一定要观察元素是否已排好位置

二分查找主要有以下两种写法：

1.1.左闭右闭[left,right]

该写法注意点：（本文不再进行基础实现讲解，可以翻看我的之前文章，有实现过程）
1.while (left <= right) 要使? <= ，因为 left == right 是有意义的，所以使? <=
2.if (nums[middle] > target) right 要赋值为 middle - 1 ，因为当前这个 nums[middle] ?定不是 target ，那么接下来要查找的左区间结束下标位置就是 middle - 1

对于leedcode这题：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

就是典型的第一类写法

下面是我对于该题的C语言解法代码：

int search(int* nums, int numsSize, int target) 
{
    int left=0;
    int right=numsSize-1;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(nums[mid]<target)
        {
            left=mid+1;
        }
        else if(nums[mid]>target)
        {
            right=mid-1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
时间复杂度： O(log n)
空间复杂度： O(1)

1.2.左闭右开[left,right)

注意点：

1.while (left < right) ，这?使? < , 因为 left == right 在区间 [left, right) 是没有意义的
2.if (nums[middle] > target) right 更新为 middle ，因为当前 nums[middle] 不等于 target ，去左区间继续寻找，?寻找区间是左闭右开区间，所以right 更新为 middle ，即：下?个查询区间不会去?较 nums[middle]。
还是刚才那题，现在我们用第二种方法实现它： 
int search(int* nums, int numsSize, int target) 
{
    int left=0;
    int right=numsSize;//注意right现在是被赋值为numsSize
    while(left<right)
    {
        int mid=(left+right)/2;
        if(nums[mid]<target)
        {
            left=mid+1;
        }
        else if(nums[mid]>target)
        {
            right=mid;//由于用边界为空，所以right=mid，而不是right=mid-1
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

补充：如果你想问有没有左开右闭的二分查找，我想说的是有，当使用的意义不大，所以作者这里就不讲了。

下面是推荐的练习题：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台? ?（69.x 的平?根）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台? ? ? ? （367.有效的完全平?数）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台? ? ? ? (34.在排序数组中查找元素的第?个和最后?个位置)

这些题可能对你有点难，请加油，我相信你一定可以的。

2.双指针法（重点）

解释：双指针法是定义两个有关联的变量，可能是指针，也可能是整数，通过他们实现对数组的操作，使得高效，快捷。

具体的我们来在题目中去感受吧！

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

对于leedcod这题，大家第一反应可能就是暴力出手，疯狂遍历数组，一个for循环不行，那我两个，再不行，再加，但是现在来看看大佬们的思路，让你直呼666……
双指针法就是这题的良方妙药，下面我带着大家用双指针来实现它
由于是数组，我们定义两个整型变量，即slow和fast，表示快慢指针
快指针：寻找新数组的元素 ，新数组就是不含有?标元素的数组
慢指针：指向更新新数组下标的位置
看代码： 
int removeElement(int* nums, int numsSize, int val) 
{
    //双指针法
    int src=0;
    int dest=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)
        {
            nums[dest++]=nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dest;
}

是不是大呼学到了。

关于双指针的使用场景，大家需要多做题，自己把握，这样慢慢可能就能感受的啥题目是考察双指针了。

来再带着大家看一题：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

对于这题，我们就直接开始双指针吧！

这题比较特殊，它是有序的，又是问平方，只需要比较负数的平方与整数平方关系即可，大家想想，如果我们定义两个指针，一个指向头，一个指向尾，是不是就可以最快的进行排好序。

看代码实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize) 
{
    *returnSize = numsSize;
    int* arr=(int*)malloc(numsSize*sizeof(int));
    int n=0;
    int m=numsSize-1;
    int c=numsSize-1;
    while(n<=m)
    {
        int i=nums[n]*nums[n];
        int j=nums[m]*nums[m];
        if(i>j)
        {
            arr[c--]=i;
            n++;
        }
        else//j>=i
        {
            arr[c--]=j;
            m--;
        }
    }
    return arr;
}
双指针?骚起来，也是?敌（转自程序员Carl）
下面给大家推荐几道好题：（不用说谢了，这种好东西，一定要拿出来共享，当时快把我写吐了）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

刷完绝对对于双指针有一定的使用感觉了。

3.滑动窗口

如果大家深入了解过数组，就一定听过数组恶魔---滑动窗口
对于滑动窗口，连leedcode上都是中等题起步
下面我们就一题进行了解：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
滑动窗?， 就是不断的调节?序列的起始位置和终?位置，从?得出我们要想的结果
我们应该可以看出，如果我们纯暴力来解决这题，就是两个for循环，但是如果用滑动窗口，一个for循环即可，下面来看看实现过程：
?先要思考 如果??个 for 循环，那么应该表示滑动窗?的起始位置，还是终?位置。 如果只??个for 循环来表示 滑动窗?的起始位置，那么如何遍历剩下的终?位置？ 此时难免再次陷? 暴?解法的怪圈。 所以只??个for 循环，那么这个循环的索引，?定是表示滑动窗?的终?位置。
在本题中实现滑动窗?，主要确定如下三点：
窗?内是什么？
如何移动窗?的起始位置？
如何移动窗?的结束位置？
窗?就是 满?其和 ≥ s 的?度最?的 连续 ?数组。
窗?的起始位置如何移动：如果当前窗?的值?于 s 了，窗?就要向前移动了（也就是该缩?了）。
窗?的结束位置如何移动：窗?的结束位置就是遍历数组的指针，也就是 for 循环?的索引.
看代码实现过程： 
int minSubArrayLen(int target, int* nums, int numsSize) 
{
    int size=0;
    int result=INT_MAX;
    int left=0;
    int sum=0;
    for(int right=0;right<numsSize;right++)
    {
        sum+=nums[right];
        while(sum>=target)
        {
            size=right-left+1;
            result=result<=size?result:size;
            sum-=nums[left++];
        }
    }
    return result==INT_MAX?0:result;
}

时间复杂度直接从O（N*N)降到了O(N),可见这种方法的强大。

推荐大家去B站看代码随想录视频，可能理解更加深入。

下面给大家推荐题目吧：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
这两题是真的难啊！！！加油
最后，给小编点赞呗kiss！

文章来源:https://blog.csdn.net/2301_79813267/article/details/135118056
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。