零基础刷代码随想录【Day1】|| 二分查找,移除元素

2023-12-28 11:35:36

我的个人主页:☆光之梦☆的博客_CSDN博客-C语言基础语法(超详细)领域博主

欢迎各位 👍点赞 ?收藏 📝评论

我的专栏:C语言基础语法(超详细)_☆光之梦☆的博客-CSDN博客(这个专栏里的平均文章质量分是95噢,基本全都是高质量文章,本博主将会长期更新c语言的语法知识,初学c语言的朋友们,可以收藏订阅一下,收藏绝对不亏噢)

目录

day1

数组理论基础

二分查找(leetcode704)

题目描述

二分查找易错点

解题思路&代码

方法1:左闭右闭

方法2:左闭右开

移除元素(leetcode27)

题目描述

解题思路&代码

方法1:暴力解法

方法2:双指针法


day1

数组理论基础

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

数组是通过下标索引的方式获取到下标下对应的数据

需要注意的是

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

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

数组的元素是不能删的,只能覆盖

内存地址,我就简单介绍一下, 0x7ffee4065820 与 0x7ffee4065824 差了一个4,就是4个字节,因为这是一个int型的数组,所以两个相邻数组元素地址差4个字节。

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

二分查找(leetcode704)

要求:要熟悉 根据 左闭右开,左闭右闭 两种区间规则 写出来的二分法

题目描述

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示:

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文章讲解:

代码随想录

视频讲解:

手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili

二分查找易错点

到底是 while(left < right) 还是 while(left <= right)?

是right = middle呢,还是right = middle - 1呢?

写二分法经常容易写乱,主要就是因为对区间的定义没有想清楚,没有理解清楚

在while循环中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则

例如

如果是用 while(left <= right)

那么当 nums[mid] > target 时 要查找的数在做左边 这时右边界 right = mid - 1;

如果是用 while(left < right)

那么当 nums[mid] > target 时 要查找的数在做左边 这时右边界 right = mid;

这就是我们要根据区间的定义来操作的原因。

写二分法,区间的定义一般为两种

  • 左闭右闭:[left, right]
  • 左闭右开:[left, right)

解题思路&代码

用二分查找解这道题目的前提是:

  1. 数组为有序数组
  2. 数组中无重复元素

因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件

二分查找两个方法

  1. 左闭右闭
  2. 左闭右开

手撕二分查找

方法1:左闭右闭
class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }

        // 定义数组的左右边界
        int left = 0;
        int right = nums.length - 1;

        // 方法1:左闭右闭
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {// 要查找的数在左边
                right = mid - 1;
            } else if (nums[mid] < target) {// 要查找的数在右边
                left = mid + 1;
            } else if (nums[mid] == target) {//正好找到 直接返回
                return mid;
            }
        }
        //没找到目标值即要查找的数不存在
        return -1;
    }
}
  • 时间复杂度:O(log n)

方法2:左闭右开
class Solution {
    public int search(int[] nums, int target) {
        //定义左边界和右边界
        int left = 0;
        int right = nums.length;
        
        // 方法2:左闭右开
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] > target){//要查找的数在左边
                right = mid;
            }else if(nums[mid] < target){//要查找的数在右边
                left = mid + 1;
            }else if(nums[mid] == target){//正好找到 直接返回
                return mid;
            }
        }
        //没找到目标值即要查找的数不存在
        return -1;
    }
}
  • 时间复杂度:O(log n)

移除元素(leetcode27)

要求:

  1. 用暴力的解法,可以锻炼一下我们的代码实现能力,建议先把暴力写法写一遍
  2. 双指针法 是本题的精髓,今日需要掌握

题目描述

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文章讲解:

代码随想录

视频讲解:

数组中移除元素并不容易! | LeetCode:27. 移除元素_哔哩哔哩_bilibili

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

数组中的位置是删除不了的 只能覆盖该位置中的数据

也就是说在下图的数组中,如果你要删除3的话 是删除不了该位置的,只能覆盖它的数据

在数组中删除元素是这样的:把4往前移动一位把3覆盖掉,再把5往前移动一位,把4覆盖掉,以此类推后面的数据全部往前移动,最后一个位置放什么都无所谓,可以放原来的数。

解题思路&代码

一遍不懂 二遍 二遍不懂就看第三遍,算法最重要的就是思路

方法1:暴力解法

这个题 暴力的解法就是使用两层for循环

第一个for循环用来:遍历数组中的所有元素

第二个for循环用来:替换数组元素的值

class Solution {
    public int removeElement(int[] nums, int val) {
        // 暴力法
        // 用一个变量来保存数组的大小
        int size = nums.length;
        for(int i = 0; i < size; i++){//第一个for循环用来遍历数组元素
            if(nums[i] == val){//发现需要移除的元素
                for(int j = i + 1; j < size; j++){//将那个数之后的所有元素向前覆盖一位
                    nums[j - 1] = nums[j];//把后一个元素赋给前一个元素所在的地址
                }
                i--;//因为下标i以后得数值都向前移动了一位,所以i也向前移动一位
                size--;//因为删除了一个元素 所以此时数组大小要-1
            }
        }
        return size;
    }
}
  • 时间复杂度:O(n^2)

方法2:双指针法

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

快指针与慢指针

快指针用来寻找新数组中的需要的元素

就是删除我们目标值之后的元素 就是新数组中的元素

当我们用快指针获取到新数组需要的元素时 我们就用慢指针来赋值给新数组

就是把快指针获取到的值 赋值给慢指针就OK了

我们要想删除数组中的某一个元素

那我们的新数组中是不是就不能包含该元素

那么当我们的快指针指向的值 不等于我们要删除的目标元素

那我们就可以把该值赋给新数组

也就是把我们快指针所获取到的值,赋值给新数组所对应的下标位置

假设我们要删除一个数组中的元素3

删除元素3完成

新数组中没有元素3

同理我们在原数组中也能执行同样的操作,可以不用new一个新的数组,直接在原数组上进行元素的移除

如本题的要求:不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地修改输入数组。

代码示例如下:

class Solution {
    public int removeElement(int[] nums, int val) {
        //快慢指针
        //慢指针slowIndex,快指针fastIndex
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex < nums.length; fastIndex++){
            if(nums[fastIndex] != val){
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}
  • 时间复杂度:O(n)

各位学习C语言的初学者,如果有问题随时都可以来问我,我会随时为您解答!欢迎大家与我一起学习,互相进步。

我的C语言专栏:C语言基础语法(超详细)_☆光之梦☆的博客-CSDN博客

创作不易,👍?+??+📝(一键三连)?是对博主最大的鼓励与支持哦。

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