189 8069 5689

【Day1】数组、704二分查找、27移除元素-创新互联

【Day1】数组、704二分查找、27移除元素
  • 数组
  • 704 二分查找
    • 版本一 左闭右闭 即[left, right]
    • 版本二 左闭右开 即[left, right)
  • 27 移除元素
    • 暴力解法
    • 双指针法

练习的题目来自力扣,顺序按照代码随想录进行。

让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:申请域名、网页空间、营销软件、网站建设、仙桃网站维护、网站推广。数组

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

  • 数组的下标都是从0开始的
  • 数组内存空间的地址是连续的(一维、二维都是连续的)
  • 数组的元素是不能删的,只能覆盖
  • 数组是随机存取的存储结构

如果使用C++的话,要注意vector 和 array的区别,vector的底层实现是array,严格来讲vector是容器,不是数组。
vector是顺序容器,其利用连续的内存空间来存储元素,但是其内存空间大小是能够改变的。
array是顺序容器,其也是利用连续的内存空间来存储元素,但它的内存空间是固定大小的,申请之后就无法改变。

704 二分查找

二分查找的前提是数组是有序数组,且数组中无重复元素。

因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。

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

题目链接:704 二分查找

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

版本一 左闭右闭 即[left, right]

[left, right] 左右两边都能取到,nums[m]不可能等于target,所以nums[m]>target,则right=m-1

// 版本一 左闭右闭即[left, right]
class Solution {public:
    int search(vector& nums, int target) {//vector好比是一个数组
        int left=0;
        int right=nums.size()-1;    //左闭右闭,下标从0开始,最后一个数就是个数减1
        while (left<=right)
        {int middle=left+((right-left)/2);  //防止溢出,等价于 (left+right)/2
            if(nums[middle]>target){right=middle-1;//target在左区间, middle是几个数值的中间数 数组这里是以下标看来值,因此下标-1
            }else if(nums[middle]left=middle+1;//target在右区间
            }else{  //nums[middle]==target
                return middle;
            }
        }
        // 未找到目标值
        return -1;
    }
};

关于下面这句代码

int middle = left + ((right - left) / 2);  //而不用mid = (left+right)/2

原因:mid = (left + right) / 2 容易溢出!因为left+right很容易超过int范围!而mid = left + (right - left) / 2 不容易溢出,所以建议以后写二分时要用mid = left + (right - left) / 2
来源:二分查找

版本二 左闭右开 即[left, right)

[left, right) 左边值能取到右边值取不到,nums[m]可能等于target,所以nums[m]>target,则right=m

// 版本二  左闭右开即[left, right)
class Solution {public:
    int search(vector& nums, int target) {int left=0;
        int right=nums.size();    //左闭右开,
        while (leftint middle=left+((right-left)>>1);  //防止溢出,(right-left)>>1相当于(right - left)/2
            if(nums[middle]>target){right=middle;//target在左区间,[left,middle)
            }else if(nums[middle]left=middle+1;//target在右区间,[middle+1,right)
            }else{  //nums[middle]==target
                return middle;
            }
        }
        // 未找到目标值
        return -1;
    }
};

下面这句代码中的 (right - left) >>1相当于(right - left)/2

int middle = left + ((right - left) >>1);

原因:还是担心left+right可能会超过基本类型的大值
来源:left + ((right -left) >> 1

27 移除元素

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

题目链接:27移除元素

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

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

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

暴力解法

暴力解法是两层for循环,一个for循环遍历数组元素 ,第二个for循环更新数组。
时间复杂度:O(n^2)
空间复杂度:O(1)

//暴力解法  两层for 循环
class Solution {public:
    int removeElement(vector& nums, int val) {int size=nums.size();
        for(int i=0;iif(nums[i]==val){for(int j=i+1;jnums[j-1]=nums[j];   //后面的数往前移
                }
                i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;
    }
};
双指针法

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

定义快慢指针

  • 快指针:寻找新数组需要的元素 ,新数组就是不含有目标元素的数组(删除目标值后的数组)
  • 慢指针:指向更新 新数组下标的位置

快指针就是用来创建新数组的,当快指针不等于目标值(要删除的数)时,那就是我们创建的新数组需要的元素,我们要更新数组,把快指针所获取的值赋给新数组所对应的下标的位置,就是把快指针给到慢指针所在的位置,慢指针就是更新新数组的位置。快指针把值赋给慢指针后,慢指针也需要向后移动一个位置来继续更新。当快指针碰到要删除的元素值时,下面的这个for循环里面的内容就不会进行,快指针继续向后移动,慢指针还在原来的位置(这一步就是进行了移除元素)

// 时间复杂度:O(n)
// 空间复杂度:O(1)
//双向指针 快慢指针
class Solution {public:
    int removeElement(vector& nums, int val) {int slowIndex=0;
        for(int fastIndex=0;fastIndexif(val!=nums[fastIndex]){nums[slowIndex++]=nums[fastIndex];
            }
        }
        return slowIndex;  //慢指针对应的下标就是新数组中的大小
    }
};

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站标题:【Day1】数组、704二分查找、27移除元素-创新互联
本文路径:http://cdxtjz.cn/article/ddgisd.html

其他资讯