草庐IT

力扣35题搜索插入位置Q35SearchInsertPosition

mrystar 2023-03-28 原文

Q35SearchInsertPosition

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

https://leetcode.cn/problems/search-insert-position

解题思路

首先考虑暴力解法，但暴力的时间复杂度是 O(n) 不符合题目要求，像这种找目标值的首先考虑二分法。二分法要注意的就是 left < right 还是left <= right 的选择问题和区间缩小时的定界。

解题如下
首先初始化为left=0，right=len，因为数组长度位置即最后一个元素后面的位置也可为答案。最初的搜索区间为[0, len]，也就是left ~ right，在搜索过程中有如下情况

  • 当中间值小于目标值时，mid和mid往左的位置都不是所要找的位置，left应等于mid+1，搜索区间变为[mid+1, right]
  • 其余情况，中间值大于等于目标值，那么mid的位置可能是要找的位置，但mid往右绝对不是要找的位置，故right变为mid，搜索区间变为[left, mid]
  • 搜索终止时，一定有left==right，也就是区间[left, right]里面一定有要找的位置，此时返回left或right任一即可。

代码

public class Q35SearchInsertPosition {
    public int searchInsert(int[] nums, int target) {
        if(null == nums || nums.length == 0){
            return 0;
        }
        int left = 0;
        int right = nums.length;
        while(left < right){
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                left = mid + 1;  //缩小区间为[mid+1, right]
            } else {
                right = mid;     //缩小区间为[left, mid]
            }
        }
        return left;
    }
}

本地测试

public class Q35SearchInsertPositionTest {
    private static final Q35SearchInsertPosition q = new Q35SearchInsertPosition();

    @Test
    public void test1(){
        assertEquals(2, q.searchInsert(new int[]{1,3,5,6}, 5));
    }

    @Test
    public void test2(){
        assertEquals(1, q.searchInsert(new int[]{1,3,5,6}, 2));
    }

    @Test
    public void test3(){
        assertEquals(4, q.searchInsert(new int[]{1,3,5,6}, 7));
    }

    @Test
    public void test4(){
        assertEquals(0, q.searchInsert(new int[]{1,3,5,6}, 0));
    }

    @Test
    public void test5(){
        assertEquals(0, q.searchInsert(new int[]{1}, 0));
    }

}

提交

SearchInsertPositionQ35rightleftmid算法与数据结构

有关力扣35题搜索插入位置Q35SearchInsertPosition的更多相关文章

  1. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  2. ruby - 正则表达式在哪个位置失败？ - 2

    我需要一个非常简单的字符串验证器来显示第一个符号与所需格式不对应的位置。我想使用正则表达式，但在这种情况下，我必须找到与表达式相对应的字符串停止的位置，但我找不到可以做到这一点的方法。(这一定是一种相当简单的方法……也许没有？)例如，如果我有正则表达式:/^Q+E+R+$/带字符串:"QQQQEEE2ER"期望的结果应该是7 最佳答案 一个想法:你可以做的是标记你的模式并用可选的嵌套捕获组编写它:^(Q+(E+(R+($)?)?)?)?然后你只需要计算你获得的捕获组的数量就可以知道正则表达式引擎在模式中停止的位置，你可以确定匹配结束

  3. ruby - 如何搜索有用的 ruby - 2

    寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是ruby​​gems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和ruby​​gems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko

  4. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  5. ruby - 如何在 Ruby 字符串中插入项目符号字符？ - 2

    我正在尝试创建一个带有项目符号字符的Ruby1.9.3字符串。str="•"+"helloworld"但是，当我输入它时，我收到有关非ASCII字符的语法错误。我该怎么做？ 最佳答案 你可以把Unicode字符放在那里。str="\u2022"+"helloworld" 关于ruby-如何在Ruby字符串中插入项目符号字符？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1195

  6. ruby - Ruby 中的必应搜索 API - 2

    我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是

  7. ruby - 下载位置 Selenium-webdriver Cucumber Chrome - 2

    我将Cucumber与Ruby结合使用。通过Selenium-Webdriver在Chrome中运行测试时，我想将下载位置更改为测试文件夹而不是用户下载文件夹。我当前的chrome驱动程序是这样设置的:Capybara.default_driver=:seleniumCapybara.register_driver:seleniumdo|app|Capybara::Selenium::Driver.new(app,:browser=>:chrome,desired_capabilities:{'chromeOptions'=>{'args'=>%w{window-size=1920,1

  8. ruby - Heroku production.log 文件位置 - 2

    我想在heroku.com上查看我的应用程序日志的内容，所以我关注了thisexcellentadvice并拥有我所有的日志内容。但是我现在很想知道我的日志文件实际在哪里，因为“log/production.log”似乎是空的:C:\>herokuconsoleRubyconsoleforajpbrevx.heroku.com>>files=Dir.glob("*")=>["public","tmp","spec","Rakefile","doc","config.ru","app","config","lib","README","Gemfile.lock","vendor","sc

  9. Ruby#index 方法 VS 二进制搜索 - 2

    给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

  10. ruby - 在 Ruby 中查找多个正则表达式匹配的模式和位置 - 2

    这应该是一个简单的问题，但我找不到任何相关信息。给定一个Ruby中的正则表达式，对于每个匹配项，我需要检索匹配的模式$1、$2，但我还需要匹配位置。我知道=~运算符为我提供了第一个匹配项的位置，而string.scan(/regex/)为我提供了所有匹配模式。如果可能，我需要在同一步骤中获得两个结果。 最佳答案 MatchDatastring.scan(regex)do$1#Patternatfirstposition$2#Patternatsecondposition$~.offset(1)#Startingandendingpo

随机推荐