草庐IT

javascript - 找到距离原点 (0, 0) 最近的 K 个点

coder 2024-12-18 原文

问题是，给定一个坐标列表，确定离原点最近的 k 个坐标的数量。

我已经能够确定点和原点之间的距离，但是在过滤最近的 k 个点时，我迷路了。我决定将此逻辑放在第二个 for 循环中，将距离数组从最近到最远排序，然后推送小于 K 的值。

function kClosest(points, k) {
    let length = [];
    let arr = [];
    let result = [];
    let a = 0;
    let b = 0;

    for (let i = 0; i < points.length; i++) {
        a = points[i][0]; //x coord
        b = points[i][1]; //y coord (y will always be second number or '1')
        length.push(parseFloat(calcHypotenuse(a, b).toFixed(4)))
        arr.push([points[i], length[i]])
    }

    function calcHypotenuse(a, b) {
        return (Math.sqrt((a * a) + (b * b)));
    }

    for (let i = 0; i < k; i++) {
        arr = arr.sort();
        result.push(arr[i][0])
    }
    return result;
}



console.log(kClosest([
    [-5, 4],
    [-6, -5],
    [4, 6]
], K = 2))

预期输出:[-5, 4], [4, 6]//我有 [-5, 4], [-6, -5]

最佳答案

对整个数组进行排序是一种浪费，甚至可能是不可能的。这很浪费，因为问题没有要求所有元素的总排序，甚至没有要求 k。元素。使用基于比较的排序进行排序需要 O(n log(n))时间。更一般地说，如果输入是数字流，将它们全部存储在内存中并对其进行排序甚至可能是不可能的。

我不太了解 JavaScript，但在一般算法领域，我们可以使用以下两种方法之一更快地解决这个问题:

  1. 使用 Max Priority Queue :创建一个最大 PQ，其顺序基于与原点的距离。继续插入最大 PQ 中的元素，每当大小超过 k 时, 删除顶部元素(最大值)。最后，PQ 将有 k最小的元素。空间复杂度:O(k) ，时间复杂度:O(n log(k)) k << n , 可能接近 O(n) .
  2. 使用Quick-select :在输入上运行快速选择 k 次。这假设输入适合内存(空间 O(n) )，但在 O(nk) 中运行时间，对于 k << n , 可能接近 O(n) .

关于javascript - 找到距离原点 (0, 0) 最近的 K 个点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54544491/

javascript找到codesectionpointsarraysalgorithmloopsreturn

有关javascript - 找到距离原点 (0, 0) 最近的 K 个点的更多相关文章

  1. ruby-on-rails - capybara ::ElementNotFound:无法找到 xpath "/html" - 2

    我正在学习http://ruby.railstutorial.org/chapters/static-pages上的RubyonRails教程并遇到以下错误StaticPagesHomepageshouldhavethecontent'SampleApp'Failure/Error:page.shouldhave_content('SampleApp')Capybara::ElementNotFound:Unabletofindxpath"/html"#(eval):2:in`text'#./spec/requests/static_pages_spec.rb:7:in`(root)'

  2. ruby - 如何找到调用当前方法的方法 - 2

    如何找到调用此方法的位置？defto_xml(options={})binding.pryoptions=options.to_hifoptions&&options.respond_to?(:to_h)serializable_hash(options).to_xml(options)end 最佳答案 键入caller。这将返回当前调用堆栈。文档:Kernel#caller.例子[0]%rspecspec10/16|===================================================62=====

  3. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  4. python - 帮我找到合适的 ruby​​/python 解析器生成器 - 2

    我使用的第一个解析器生成器是Parse::RecDescent，它的指南/教程很棒，但它最有用的功能是它的调试工具，特别是tracing功能(通过将$RD_TRACE设置为1来激活)。我正在寻找可以帮助您调试其规则的解析器生成器。问题是，它必须用python或ruby​​编写，并且具有详细模式/跟踪模式或非常有用的调试技术。有人知道这样的解析器生成器吗？编辑:当我说调试时，我并不是指调试python或ruby​​。我指的是调试解析器生成器，查看它在每一步都在做什么，查看它正在读取的每个字符，它试图匹配的规则。希望你明白这一点。赏金编辑:要赢得赏金，请展示一个解析器生成器框架，并说明它的

  5. ruby - 实现k最近邻需要哪些数据？ - 2

    我目前有一个reddit克隆类型的网站。我正在尝试根据我的用户之前喜欢的帖子推荐帖子。看起来K最近邻或k均值是执行此操作的最佳方法。我似乎无法理解如何实际实现它。我看过一些数学公式(例如k表示维基百科页面)，但它们对我来说并没有真正意义。有人可以推荐一些伪代码，或者可以查看的地方，以便我更好地了解如何执行此操作吗？ 最佳答案 K最近邻(又名KNN)是一种分类算法。基本上，您采用包含N个项目的训练组并对它们进行分类。如何对它们进行分类完全取决于您的数据，以及您认为该数据的重要分类特征是什么。在您的示例中，这可能是帖子类别、谁发布了该项

  6. ruby - 404 未找到，但可以从网络浏览器正常访问 - 2

    我在这方面尝试了很多URL，在我遇到这个特定的之前，它们似乎都很好:require'rubygems'require'nokogiri'require'open-uri'doc=Nokogiri::HTML(open("http://www.moxyst.com/fashion/men-clothing/underwear.html"))putsdoc这是结果:/Users/macbookair/.rvm/rubies/ruby-2.0.0-p481/lib/ruby/2.0.0/open-uri.rb:353:in`open_http':404NotFound(OpenURI::HT

  7. ruby-on-rails - 通过 has_many 找到 Rails :through - 2

    我正在寻找一种方法来通过关联查询基于has_many中的子项的模型。我有3个模型:classConversation我需要找到参与者匹配一组ID的对话。这是我目前拥有的(不工作):Conversation.includes(:participants).where(participants:params[:participants]) 最佳答案 听起来你只是想要对话，如果是这样你可以加入。Conversation.joins(:participants).where(:users=>{:id=>params[:participant

  8. ruby - capybara 无法通过 id 找到元素 - 2

    capybara找不到在我的cucumber测试中用它的id标记。当我save_and_open_page时，我能够看到该元素.但我无法通过has_css?找到它或find:pry(#)>page.html.scan(/notice_sent/).count=>1pry(#)>page.html.scan(/id=\"notice_sent\"/).count=>1pry(#)>page.find('#notice_sent')Capybara::ElementNotFound:Unabletofindcss"#notice_sent"from/Users/me/.gem/ruby/2

  9. ruby-on-rails - Ruby 如何知道在哪里可以找到所需的文件？ - 2

    这里还有一个新手问题:require'tasks/rails'我在每个Rails项目的根路径中的Rakefile中看到了这一行。我猜这行用于要求vendor/rails/railties/lib/tasks/rails.rb加载所有rake任务:$VERBOSE=nil#LoadRailsrakefileextensionsDir["#{File.dirname(__FILE__)}/*.rake"].each{|ext|loadext}#LoadanycustomrakefileextensionsDir["#{RAILS_ROOT}/lib/tasks/**/*.rake"].so

  10. ruby - 在 Mechanize 中使用 JavaScript 单击链接 - 2

    我有这个:AccountSummary我想单击该链接，但在使用link_to时出现错误。我试过:bot.click(page.link_with(:href=>/menu_home/))bot.click(page.link_with(:class=>'top_level_active'))bot.click(page.link_with(:href=>/AccountSummary/))我得到的错误是:NoMethodError:nil:NilClass的未定义方法“[]” 最佳答案 那是一个javascript链接。Mechan

随机推荐