【LC刷题】DAY01:704. 二分查找、27. 移除元素

2024-06-06 01:04

本文主要是介绍【LC刷题】DAY01:704. 二分查找、27. 移除元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【LC刷题】DAY01:704. 二分查找、27. 移除元素

文章目录

  • 【LC刷题】DAY01:704. 二分查找、27. 移除元素
    • 704. 二分查找 [link](https://leetcode.cn/problems/binary-search/description/)
      • 第一思路:
      • 优化思路
    • 27. 移除元素 [link](https://leetcode.cn/problems/remove-element/description/)
      • 第一思路--快慢指针
      • 优化思路-相遇指针

704. 二分查找 link

第一思路:

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;int mid = left + right >> 1;while(left <= right){mid = left + right >> 1;if(nums[mid] == target){return mid;}if(nums[mid] > target){right = mid - 1;}else{left = mid + 1 ;}}return -1;}
};

时间复杂度 O(nlogn)
空间复杂度 O(1)

优化思路

暂时无需优化

27. 移除元素 link

第一思路–快慢指针

class Solution {
public:int removeElement(vector<int>& nums, int val) {int count = nums.size();int left = 0;for(int right = 0; right < count ; right ++){if(nums[right] != val){nums[left] = nums[right];left ++;}}return left;}
};

时间复杂度 O ( n ) O(n)O(n)
空间复杂度 O ( 1 ) O(1)O(1)

优化思路-相遇指针

public:int removeElement(vector<int>& nums, int val) {int left = 0, right = nums.size() ;while(left < right){if (nums[left] == val){nums[left] = nums[right -1];right --;}else{left ++;}}return left;}
};

时间复杂度 O ( n ) O(n)O(n)
空间复杂度 O ( 1 ) O(1)O(1)

这篇关于【LC刷题】DAY01:704. 二分查找、27. 移除元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1034673

相关文章

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c