草庐IT

c++ - 给定一个排序数组和一个参数 k，求在线性时间内大于或等于 k ​​的两个数之和的计数

coder 2024-02-15 原文

我试图在一个数组中找到和等于 k ​​的所有对。我当前的解决方案需要 O(n*log(n)) 时间(下面的代码片段)。任何人都可以帮助我找到更好的解决方案，O(n) 或 O(lgn) 可能是(如果存在)

  map<int,int> mymap;
  map<int,int>::iterator it;

  cin>>n>>k;

  for( int i = 0 ; i < n ; i++ ){

    cin>>a;
    
    if( mymap.find(a) != mymap.end() )
        mymap[a]++;
    else    
        mymap[a] = 1;
        
   }

   for( it = mymap.begin() ; it != mymap.end() ; it++ ){
            
    int val = it->first;
    
    if( mymap.find(k-val) != mymap.end() ){
        
        cnt += min( it->second, mymap.find(k-val)->second );
        it->second = 0;
        
    }
    
 }
  cout<<cnt;

最佳答案

另一种方法在最好的情况下采用 O(log n)，在最坏的情况下对正数采用 O(nlog n)，可以通过这种方式完成:

  1. 在数组中找到等于 k/2 的元素，或者如果它不存在则找到大于 k/2 的最小值。我们会对包含此元素和所有更大元素的所有组合感兴趣，因为当 p>= k/2 且 s>=k/2 时 p + s >= k。数组已排序，因此可以使用经过一些修改的二分查找。此步骤将花费 O(log n) 时间。
  2. 所有小于 k/2 + 大于或等于“镜像元素”的元素(根据中值 k/2)我们也会感兴趣，因为当 p=k/2- 时 p + s >= k t 和 s>=k/2+t。这里我们需要遍历小于 k/2 的元素并找到它们的镜像元素(二分查找)。如果镜像元素大于最后一个数组，则应停止循环。

例如我们有数组 {1,3,5,8,11} 和 k = 10，所以在第一步我们将有 k/2 = 5 和对 {5,7}，{8,11} , {8, 11}。这些对的数量将通过公式 l * (l - 1)/2 计算，其中 l = 元素数量 >= k/2。在我们的例子中 l = 3，所以计数 = 3*2/2=3。

对于 3 的第二步，镜像元素将为 7(5-2=3 和 5+2=7)，因此对 {3, 8} 和 {3, 11} 会感兴趣。对于 1 个数字镜像将是 9(5-4=1 和 5+4=9)，因此 {1, 11} 是我们寻找的。

因此，如果 k/2 < 第一个数组元素，则此算法的复杂度为="" o(log="">

对于负数，算法会稍微复杂一些，但也可以用相同的复杂度求解。

关于c++ - 给定一个排序数组和一个参数 k，求在线性时间内大于或等于 k ​​的两个数之和的计数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30892930/

给定之和mymapsection的c++arraysalgorithmsum

有关c++ - 给定一个排序数组和一个参数 k，求在线性时间内大于或等于 k ​​的两个数之和的计数的更多相关文章

  1. ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

  2. ruby-on-rails - Rails - 一个 View 中的多个模型 - 2

    我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何

  3. ruby-on-rails - 渲染另一个 Controller 的 View - 2

    我想要做的是有2个不同的Controller，client和test_client。客户端Controller已经构建，我想创建一个test_clientController，我可以使用它来玩弄客户端的UI并根据需要进行调整。我主要是想绕过我在客户端中内置的验证及其对加载数据的管理Controller的依赖。所以我希望test_clientController加载示例数据集，然后呈现客户端Controller的索引View，以便我可以调整客户端UI。就是这样。我在test_clients索引方法中试过这个:classTestClientdefindexrender:template=>

  4. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

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

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

  6. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

  7. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？

  8. ruby-on-rails - Rails - 从另一个模型中创建一个模型的实例 - 2

    我有一个正在构建的应用程序，我需要一个模型来创建另一个模型的实例。我希望每辆车都有4个轮胎。汽车模型classCar轮胎模型classTire但是，在make_tires内部有一个错误，如果我为Tire尝试它，则没有用于创建或新建的activerecord方法。当我检查轮胎时，它没有这些方法。我该如何补救？错误是这样的:未定义的方法'create'forActiveRecord::AttributeMethods::Serialization::Tire::Module我测试了两个环境:测试和开发，它们都因相同的错误而失败。 最佳答案

  9. ruby - 用 Ruby 编写一个简单的网络服务器 - 2

    我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不，不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本，提供另一个脚本，它将在其标准输入上获取请求，并在其标准输出上返回完整的响应。到目前为止一切顺利，但事实证明这真的很脆弱，因为它在第二个请求上中断并出现错误:/usr/b

  10. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

随机推荐