代码随想录day1 | 704.二分查找 27.移除元素

这篇具有很好参考价值的文章主要介绍了代码随想录day1 | 704.二分查找 27.移除元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、二分解题技巧

1、二分易错点

1、循环变量

while(left < right) 还是while(left <=right)

2、判断条件

if(num[mid] > tar) mid = right 还是 mid = right -1

2、循环不变量

[left, right]
[left, right)
(left, right]

3、左闭右闭写法

当时左闭右闭时,while循环里面的条件,我们可以先假设,有等号即有left=right的情况,例如[1,1]这个区间,那么循环是要进入里面的,所以要取得等号。
代码随想录day1 | 704.二分查找 27.移除元素,笔试强训,算法,数据结构
判断的时候,nums[mid]>tar,那么必然tar不在右半区间,所以right=mid-1
代码随想录day1 | 704.二分查找 27.移除元素,笔试强训,算法,数据结构
nums[mid]<tar,那么必然tar不在左半区间,所以left=mid+1
代码随想录day1 | 704.二分查找 27.移除元素,笔试强训,算法,数据结构

## 模板
left=0
right=size-1
while(left<=right)
{
	int mid=(left+right)/2;
	if(nums[mid]>tar)
	{
		right=mid-1;
	}
	else if(nums[mid]<tar)
	{
		left=mid+1;
	}
	else
	{
		return mid;
	}
}
return -1;

4、左闭右开写法

例如[1,1),既包含1又不包含1,这是个合法的区间吗?所以while(left < right)即可。

判断的时候,因为nums[mid]>tar,所以下一次搜索的时候,区间中mid必然不会在这个左半区间,所以right=mid。
当nums[mid]<tar,因为是左闭右开,明确了tar是大于nums[mid]的,那么下一次搜索的区间的左边界必然是left=mid+1。

right的取值也要注意,因为咱的区间是不包含右边界的,但是还是要包含所有的数字,right相当于变大了1,所以right=size

## 模板
left=0
right=size
while(left<=right)
{
	int mid=(left+right)/2;
	if(nums[mid]>tar)
	{
		right=mid;
	}
	else if(nums[mid]<tar)
	{
		left=mid+1;
	}
	else
	{
		return mid;
	}
}
return -1;

二、题

1、二分查找

704.二分查找

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

2、移除元素

27.移除元素

删除元素并不是删除,而是覆盖,erase这个操作是O(N)的时间复杂度。
暴力法:O(N2) 的时间复杂度,两层for循环。

// 暴力  n^2 超时了
class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int size = nums.size();
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == val)
            {
                // 将整个剩余的数组,整体移动一位
                for (int j = i + 1; j < nums.size(); j++)
                {
                    nums[j - 1] = nums[j];// 从j -1 开始为了防止越界
                }
                i--;
                size--;
            }
        }
        return size;
    }
};

双指针解法:O(N)
fast快指针:用来获取新数组中的元素,新数组就是不含有目标元素的数组
slow慢指针:用来获取新数组中需要更新的位置文章来源地址https://www.toymoban.com/news/detail-552399.html

class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int fast = 0;
        int slow = 0;
        for (fast = 0; fast < nums.size(); fast++)
        {
        	// 不是我们需要找寻的元素,就更新原数组
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            // 找到 nums[fast]==val 我们就不执行更新操作,而是直接变成fast++
        }
        return slow;
    }
};

到了这里,关于代码随想录day1 | 704.二分查找 27.移除元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录第一天 | LeetCode704.二分查找,LeetCode 27.移除元素

    数组理论基础要点: 数组也是数据结构的一种, 是存放在连续内存空间上的相同类型数据的集合。 数组注意点: 数组下标都是从0开始的。 数组内存空间的地址是连续的。 因为上述两点, 数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要

    2024年02月08日
    浏览(50)
  • 代码随想录 LeetCode数组篇 二分查找

    # (简单)704. 二分查找 题目链接 代码随想录 - 二分查找思路 二分查找,思路很简单,但是在while循环left和right的比较是写=还是,还有right=mid还是right=mid-1容易混淆 需要想清楚对区间的定义,是[left,right],还是[left,right) (版本一,左闭右闭版本) (版本二,左闭右开) 题目

    2024年02月02日
    浏览(50)
  • Day1 LeetCode 704.二分查找 27.移除元素

    704.二分查找 题目链接: 力扣 文章讲解: 代码随想录 视频讲解: 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili 看完随想录之后的想法 两种情况1.左闭右闭  [ ]  2.左闭右开 [ )  当定义时为左闭右闭时,while中if的条件可以

    2024年02月15日
    浏览(40)
  • day1-数组part01| 704. 二分查找、27. 移除元素

    数组是存放在连续内存空间上的相同类型数据的集合。 数组下标从0开始 数组内存空间的地址是连续的 1、vector是顺序容器,其利用连续的内存空间来存储元素,但是其 内存空间大小是能够改变的 。 2、array是顺序容器,其也是利用连续的内存空间来存储元素,但它的 内存空

    2024年02月05日
    浏览(46)
  • 算法刷题营【Day1】:: 704.二分查找:二分法详谈与相关刷题

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:704. 二分查找 2. 题解参考(模板写法) - - 2.1 方法一:左闭右闭写法 - - 2.2 方法二:左闭右开写法 3. 模板解释:左闭右闭 - - 3.1 区间划定 - - 3.2 left 、right 移动问题 - - 3.3 循环条件

    2024年02月04日
    浏览(45)
  • 代码随想录Day58

    昨天因为志愿活动和笔试耽误了一整天,今天继续学习动规解决子序列问题。 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,

    2023年04月27日
    浏览(50)
  • 代码随想录day59

    647. 回文子串 给你一个字符串  s  ,请你统计并返回这个字符串中  回文子串  的数目。 回文字符串  是正着读和倒过来读一样的字符串。 子字符串  是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不

    2024年02月07日
    浏览(45)
  • 代码随想录day44

    完全背包 其实就是每个物品可以使用无数次,给我们一个容器,装满这个容器的最大价值是多少。 思路: 如果求组合数就是外层for循环遍历物品,内层for遍历背包。 如果求排列数就是外层for遍历背包,内层for循环遍历物品。 完全背包的组合和排序 518. 零钱兑换 II 题目 给你

    2023年04月17日
    浏览(61)
  • 代码随想录day02

    ● 力扣题目链接 ● 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 思路 ● 暴力排序,时间复杂度O(n + nlogn) ● 使用双指针,时间复杂度O(n) 代码 ● 力扣题目链接 ● 给定一个含有 n 个正整数的数组和一个正整

    2024年02月13日
    浏览(47)
  • 代码随想录Day62

    今天继续学习单调栈解决相关问题。 nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。 对于每个 0 = i nums1.length ,找出满足 nums1

    2024年02月01日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包