草庐IT

二分查找 & 移除元素

neverlate 2023-03-28 原文

一、二分查找

1.二分查找方法概述

  • 二分查找是针对有序数组的一种查找方式。是利用(letf+right)/2 = mid的方式来对半缩短搜索范围的一种方法,一次查找,搜索的范围就会减半。相较于简单查找找寻一个target需要n步,则二分查找则最多只需查找log2n步。

2.具体实现

方法一

点击查看代码
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;
        while(left <= right){
            int mid = (right+left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid -  1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}

方法二

点击查看代码
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
        }
        return -1;
    }
}

3.要点总结

1.关于length是否-1的问题

  • length是否-1取决于区间是左闭右闭区间( [ ],还是左闭右开区间( [ ) ).当选取左闭右闭区间( [ ]时,length则需要-1,因为搜索区间包含右边界值,即整个数组下标都能取到则length需要-1。如果是左闭右开区间( [ ) )length则不需要-1,因为右边界值不包含在搜索区间内,右边界值的取值无意义。

2.关于循环条件letf是<=还是<的问题

  • 当区间是左闭右闭区间( [ ]left则取<= right。当区间是左闭右开区间( [ ) )时,则不取=

3.关于赋值是赋mid的还是mid-1的问题

  • 当区间是左闭右闭区间( [ ]时,mid则需要-1,因为mid包含在有效值区间,已经排除。当区间是左闭右开区间( [ ) )时,mid则不需要-1,因为mid的值不包含在有效的搜索区间内,无需排除,所以无需-1

二、移除元素

1.方法概述

方法一:快慢“指针”法

  • 定义一个fast下标和slow下标,两下标同时从0下标处用来寻找需要删除的val值,fast搜索需要删除的val值,如果fast为需要删除的值则fast++slow不动,当fast不是需要删除的val值时,证明该值是返回数组中需要的值,将fast的值赋给slow,然后slow++。当fast <数值长度时说明遍历完毕,返回slow下标即为新数组的大小值。

方法一:头尾“指针”交换法(自创)

  • 定义一个头下标start和尾下标end,分别从数组的0下标处和末端下标处进行搜索需要删除的val值。目的是将前排纯在的val值移到数组内的最后。有四种情况,一是start对应值和end对应值相等则end--。二是start对应值和end对应值都不相等则start++。三是当satrt的对应值不是val而end的对应值是val的时候,end--start++。最后当start的对应值等于val的时且end的值不等于val值时,进行数值交换。最终start对应值就是新数组的长度。

2.具体实现

方法一

点击查看代码
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

方法二

点击查看代码
class Solution {
    public int removeElement(int[] nums, int val) {
         int start = 0;
        int end = nums.length-1;
        while(start <= end){
            if(nums[start] == val &&  nums[end] != val ){
                int tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
                start++;
                end--;
            } else if (nums[start] != val && nums[end] == val  ) {
                end--;
                start++;
            }else if(nums[start] != val && nums[end] != val ){
                start++;
            }else{
                end--;
            }
        }
        return start;
    }     
}

3.要点总结

  • 首先需要明白的时数组的相关知识,如数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。然后重点是双指针的思想方法。

仅供个人参考,欢迎批评指正!

有关二分查找 & 移除元素的更多相关文章

  1. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

    我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身,new.html.erb,有代码:当我运行rspec时,它失败了:1)messages/new.html.erbshou

  2. ruby-on-rails - 由于 "wkhtmltopdf",PDFKIT 显然无法正常工作 - 2

    我在从html页面生成PDF时遇到问题。我正在使用PDFkit。在安装它的过程中,我注意到我需要wkhtmltopdf。所以我也安装了它。我做了PDFkit的文档所说的一切......现在我在尝试加载PDF时遇到了这个错误。这里是错误:commandfailed:"/usr/local/bin/wkhtmltopdf""--margin-right""0.75in""--page-size""Letter""--margin-top""0.75in""--margin-bottom""0.75in""--encoding""UTF-8""--margin-left""0.75in""-

  3. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗?当我运行compasswatch时,它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行?文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们?我自己编译的.sass文件编译成compiled/t

  4. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据,就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理?我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题;这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML,但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中,将我的XML代码修改为

  5. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本,我按照提供的说明安装了arubagem。它在我的Gemfile中,我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作,我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了,但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  6. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他,以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时,出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

  7. ruby-on-rails - 如何优雅地重启 thin + nginx? - 2

    我的瘦服务器配置了nginx,我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例,但找不到好的解决方案。有没有人能做到这一点? 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器,例如server{listen80;server

  8. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案? - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  9. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切,所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时,我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗?我正在使用OSX并安装了rvm。 最佳答案 或者,您可以只使用“require”,它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

  10. ruby - 无法让 RSpec 工作—— 'require' : cannot load such file - 2

    我花了三天的时间用头撞墙,试图弄清楚为什么简单的“rake”不能通过我的规范文件。如果您遇到这种情况:任何文件夹路径中都不要有空格!。严重地。事实上,从现在开始,您命名的任何内容都没有空格。这是我的控制台输出:(在/Users/*****/Desktop/LearningRuby/learn_ruby)$rake/Users/*******/Desktop/LearningRuby/learn_ruby/00_hello/hello_spec.rb:116:in`require':cannotloadsuchfile--hello(LoadError) 最佳

随机推荐