代码随想录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日
    浏览(56)
  • 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)
  • 代码随想录day01

    ● 思维不难,主要是考察对代码的掌控能力 ● 内存中的存储方式:存放在连续内存空间上的相同类型数据的集合 ● 数组可以通过下标索引获取到下标对应的数据 ● 数组下标从0开始 ● 因为内存空间地址连续,因此删除或增加元素的时候,难免移动其他元素地址 ● Java中的

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

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

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

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

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

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

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

    昨天因为准备面试所以咕咕了一天。今天继续学习动规算法,尽管背包问题已经结束但其中的各类思想仍需要进一步理解。 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两

    2023年04月14日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包