首页 > 编程语言 >算法学习Day1,二分查找,移除元素

算法学习Day1,二分查找,移除元素

时间:2023-12-13 18:22:05浏览次数:40  
标签:二分 right nums int Day1 middle 移除 目标值 left

Day1二分查找,移除元素

By HQWQF 2023/12/13

笔记


704. 二分查找

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

解法:使用二分查找来在一个有序的数组中找到指定元素的下标。

根据数据边界的不同,二分查找有两种写法。

区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。

两种写法的区别

  • 区间left right 的初始值
  • 循环条件
  • 区间缩小时left right 的新值

左闭右闭[left, right]写法

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]
        // 当left==right,区间[left, right]依然有效,所以用 <=
        //查找左闭右闭区间时,出现left==right的情况意味着只剩下了一个元素
        while (left <= right) 
        { 
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) 
            {
                right = middle - 1; // target 在左区间,所以[left, middle - 1]
            } else if (nums[middle] < target) 
            {
                left = middle + 1; // target 在右区间,所以[middle + 1, right]
            } else 
            { 
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

左闭右开[left, right) 写法

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
        // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
        // 查找区间[left, right)时,nums[right]是不被考虑的
        while (left < right) 
        { 
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) 
            {
                right = middle; // target 在左区间,在[left, middle)中
                //由于左闭右开的区间将nums[right] 排除在外,所以要将 right = middle,使nums[middle-1]参与到比较中
            } else if (nums[middle] < target) 
            {
                left = middle + 1; // target 在右区间,在[middle + 1, right)中
            } else 
            { 
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

注释

  • 二分查找的本质是不断缩小查找区间,二分查找的循环条件不成立意味着将区间缩小过头了都没有找到目标值
  • 使用int middle = left + ((right - left) / 2);而不使用(left + right)/2是为了防止溢出

27. 移除元素

原地移除数组所有数值等于目标值的元素,并返回移除后数组的新长度。

解法:暴力法或快慢指针法

暴力法:

暴力遍历的方法会遍历所有元素,碰到目标值就将其后的元素全部前移一位,然后继续遍历

两层for循环,第一层for循环遍历数组元素 ,检测到目标值就进入第二层for循环更新数组。

// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int size = nums.size();
        for (int i = 0; i < size; i++) 
        {
            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)
// 空间复杂度:O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) 
        {
        //普通的情况/if成立/没有遍历到目标值时,两个指针同步移动,
        //如果该if不成立/检测到目标值时,慢速指针会慢一位,达到覆盖的效果
            if (val != nums[fastIndex]) 
            {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;//上面这个if执行的次数=slowIndex的值=不等于目标值的元素,即删除目标值后的新长
    }
};

相向双指针方法

另外还有相向双指针方法,这个方法可以确保移动最少元素,代价是会改变元素的顺序

// 时间复杂度:O(n)
// 空间复杂度:O(1)
 int removeElement(vector<int>& nums, int val) 
 {
        int leftIndex = 0;
        int rightIndex = nums.size() - 1;
        
        while (leftIndex <= rightIndex) 
        {
            // 找左边等于val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] != val){
                ++leftIndex;
            }
            // 找右边不等于val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] == val) {
                -- rightIndex;
            }
            // 将右边不等于val的元素覆盖左边等于val的元素
            if (leftIndex < rightIndex) {
                nums[leftIndex++] = nums[rightIndex--];
            }
            
        }
        return leftIndex;   
        // leftIndex即是数组新长
        //因为循环终止时,leftIndex = rightIndex+1,而rightIndex=nums.size()-1-等于目标值的元素个数
        //所以leftIndex 就等于nums.size()-等于目标值的元素个数,即不等于目标值的元素个数

标签:二分,right,nums,int,Day1,middle,移除,目标值,left
From: https://www.cnblogs.com/HQWQF/p/17899663.html

相关文章

  • 代码随想录算法训练营Day1 | 704.二分查找、27.移除元素
    LeetCode704.二分查找二分查找是一种基础的算法,其核心思想在高中数学中就已经被大家所熟知了,然而对于代码的实现,其细节问题常常令人头疼,比如while循环的条件是什么?middle是该+1还是-1?这些问题需要有一个清晰的认知。题目链接如下:704.二分查找Carl的讲解链接:二分查找算法......
  • pydantic.errors.PydanticImportError,'pydantic:compiled' 在 Pydantic 版本 2 中已被
    今天编译python程序时pyinstaller-F--version-filefile_version_info.txtMelliferaCMD.py收到错误:58759INFO:Loadingmodulehook'hook-pydantic.py'from'D:\\env\\fbt\\Lib\\site-packages\\_pyinstaller_hooks_contrib\\hooks\\stdhooks'......
  • 第八届蓝桥杯赛题 分巧克力(用二分法实现)
    今日一道编程题  第八届蓝桥杯赛题中的分巧克力问题(用二分法实现)问题描述如下:儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有N块巧克力,其中第i块是HixWi的方格组成的长方形。为了公平起见,小明需要从这N块巧克力中切出K块巧克力分给......
  • Leetcode刷题day12-二叉树.前中后序遍历
    递归法实现前.中.后序遍历代码随想录(programmercarl.com)解题思路前序遍历:头->左->右中序遍历:左->头->右后序遍历:左->右->头递归法实现流程:1.定义递归函数;2.寻找递归终止条件;3.设计单层递归模块classSolution(): def__init__(self,val=0,left=None,right=None): sel......
  • Leetcode刷题day11-栈.滑窗最大值.出现次数前K的元素
    239.滑动窗口最大值239.滑动窗口最大值-力扣(LeetCode)给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。示例1:输入:nums=[1,3,......
  • 前端学习DAY1 HTML5基础(1)(b站pink老师)
    一、HTML简介1.网页 1.1什么是网页  网站是网页的集合,网页是网站中的一“页”(构成网站的基本元素)。 网页由图片、链接、文字、声音、视频等元素构成,通常是HTML格式的文件(.htm.或html后缀),通过浏览器来阅读。 1.2 什么是HTMLHTML(超文本标记语言),它是用来描述网页的......
  • 冲刺(day1)
    一、团队成员任务分配为了更好地推进项目,我们继续按之前任务分工进行:张钰权:负责实现公文发送和公文接受功能。周绍坤:负责实现用户认证和用户管理功能。张爽:负责实现账户权限管理。王熠名:负责实现公文编辑功能。董子瑄:负责实现日志管理功能,并初步设计了粗糙的网页界面。......
  • javaweDay1补充
    1.<label>标签可以使label标签中所包含的任何区域都可以聚焦到一个点如果没有label则必须点击那个圆圈才可以选上,而若有点击男也可以选中。2.下图中value后跟的值表明勾选男的时候提交表单的提交为1若改为男则是男3select定义下拉列表,option定义列表项 4.<textarea>文本......
  • day12栈与队列
    239.滑动窗口最大值;347.前K个高频元素;总结1滑动窗口最大值1.1思路封装一个deque类:主要构造pop、push的逻辑然后使用循环来进行遍历,更新最大值1.2代码二刷补充2前K个高频元素给定一个非空的整数数组,返回其中出现频率前k高的元素。示例1:输入:nums=[1,1,1,......
  • day19 atm项目 shopping()
    fromatm.lib_common.file_handleimport*fromatm.lib_common.moner_enquiryimport*defgoods_show():"""商品名称及价格获取"""goods=file_r(r"F:\pylearn\atm\api\商品列表.txt")#print(goods)goodslist_len=len......