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

我的个人主页：☆光之梦☆的博客_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博客

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