代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素

Pang Pang Zhu 2023-09-04 原文

704.二分查找

方法一：暴力遍历

var search=function(nums,target){
  for(var i=0;i<=nums.length-1;i++){
    if(nums[i]==target){
      return i
    }
  }
  return -1
}

方法二：二分法

使用二分法的条件：

有序数组
无重复值

二分法的两种写法

左闭右闭 [left,right]
1. while (left <= right) <=的原因？
  [left,right]的条件下，当left=right，仍然在此区间内
2. if (nums[mid] > target)
  right=mid-1还是right=mid
  [left,rght]的条件下，当right=mid时，nums[mid] > target是肯定的，则使用right=mid-1可以避免重复进入判断
  **left = mid + 1
  
  **[left,rght]的条件下，当left=mid时，nums[mid] <target是肯定的，则使用left=mid+1可以避免重复进入判断
3. mid= left + ((right - left) >> 1)
  位运算，相当于/2

//[left,right]
var search = function(nums, target) {
    // right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
    let mid, left = 0, right = nums.length - 1;
    // 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
    while (left <= right) {
        // 位运算 + 防止大数溢出
        mid = left + ((right - left) >> 1);
        // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1；如果右边界更新为mid，那中间数还在下次查找范围内
        if (nums[mid] > target) {
            right = mid - 1;  // 去左面闭区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右面闭区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};

左闭右开[left,right)
1. while (left < right) <的原因？
  [left,right)的条件下，当left=right，不在此区间内
2. if (nums[mid] > target)
  right=mid-1还是right=mid
  [left,rght)的条件下，当right=mid时，nums[mid] 不会进入判断，则使用right=mid
  **left = mid + 1
  
  **[left,rght)的条件下，当left=mid时，nums[mid] <target是肯定的，则使用left=mid+1可以避免重复进入判断
3. mid= left + ((right - left) >> 1)
  位运算，相当于/2

// [left,right)
var search = function(nums, target) {
    let left=0
    let right=nums.length
    let mid=0
    while(left<right){
        mid=left+((right-left)>>1)
        if(nums[mid]>target){ 
            right=mid
        }else if(nums[mid]<target){
            left=mid+1
        }else{
            return mid
        }
    }
    return -1
};

补充

mid= left + ((right - left) >> 1) 与 mid= left + ((right - left) / 2) 的区别

*数组中的“下标号”是从0开始的正整数。*
*面对奇数项时，mid经过（/2）运算会出现浮点数，所以/2 向下取整 >>1位运算不影响*
*修改后* mid=Math.floor( left + ((right - left) / 2) )

个人更推荐位运算

27.移除元素

题目链接：27.移除元素

数组基础

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

方法一：暴力解法

遍历数组，当数组值等于val时，将后面不等于val的值，覆盖上来，同时，数组长度缩短

var removeElement = function(nums, val) {
  var size=nums.length
  for(var i=0;i<size;i++){
    if(nums[i]==val){
      for(var j=i+1;j<size;j++){
        nums[i]=nums[j]
      }
      i--
      size--
    }
  }
  return size
  
};

方法二：双指针

有快指针和慢指针，快指针遍历数组，慢指针表示当前所在的位置
通过快指针寻找不等于val的值，再覆盖道到指针所在的当前位置，slow++

var removeElement = function(nums, val) {
  var slow=0
  for(var fast=0;fast<nums.length;fast++){
    if(nums[fast]!=val){
      nums[slow]=nums[fast]
      slow++
    }
  }
  return slow
  
};

有关代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素的更多相关文章

ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2
在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has
ruby-on-rails - 浏览 Ruby 源代码 - 2
我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru
ruby - 模块嵌套代码风格偏好 - 2
我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。最佳答案这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的
ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？最佳答案是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
ruby - Net::HTTP 获取源代码和状态 - 2
我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。最佳答案在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur
程序员如何提高代码能力？ - 2
前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源
7个大一C语言必学的程序 / C语言经典代码大全 - 2
嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来
git使用常见问题（提交代码，合并冲突） - 2
文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g
ruby - 这两段代码有什么区别？ - 2
打印1:defsum(i)i=i+[2]end$x=[1]sum($x)print$x打印12:defsum(i)i.push(2)end$x=[1]sum($x)print$x后者是修改全局变量$x。为什么它在第二个例子中被修改而不是在第一个例子中？类Array的任何方法(不仅是push)都会发生这种情况吗？最佳答案变量范围在这里无关紧要。在第一段代码中，您仅使用赋值运算符=为变量i赋值，而在第二段代码中，您正在修改$x(也称为i)使用破坏性方法push。赋值从不修改任何对象。它只是提供一个名称来引用一个对象。方法要么是破坏性

代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素

704.二分查找

方法一：暴力遍历

方法二：二分法

补充

相关题目推荐

27.移除元素

数组基础

方法一：暴力解法

方法二：双指针

相关题目推荐

有关代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素的更多相关文章

随机推荐