jjzjj

c++ - 用于查找多数元素的分而治之算法？

coder 2024-02-10 原文

如果超过一半的元素相同，则称数组具有多数元素。是否存在用于确定数组是否具有多数元素的分而治之算法？

我通常会执行以下操作，但不会使用分而治之。我不想使用 Boyer-Moore算法。

int find(int[] arr, int size) {
    int count = 0, i, mElement;

    for (i = 0; i < size; i++) {
        if (count == 0) mElement = arr[i];

        if (arr[i] == mElement) count++;
        else count--;
    }

    count = 0;
    for (i = 0; i < size; i++) {
        if (arr[i] == mElement) count++;
    }

    if (count > size / 2) return mElement;
    return -1;
}

最佳答案

我至少能看到一种分而治之的方法。

首先找到中位数，例如使用 Hoare 的 Select 算法。如果一个值构成大多数元素，则中位数必须具有该值，因此我们刚刚找到了我们正在寻找的值。

从那里找到(例如)第 25 个和第 75 个百分位数的项目。同样，如果存在多数元素，则至少其中之一需要与中位数具有相同的值。

假设您还没有排除多数元素，您可以继续搜索。例如，假设第 75 个百分位数等于中位数，但第 25 个百分位数不是。

然后继续搜索第 25 个百分位和中位数之间的项目，以及第 75 个百分位和末尾之间的项目。

继续寻找每个分区的中位数，该分区必须包含与中位数具有相同值的元素的末尾，直到您确认或否认多数元素的存在。

顺便说一句:我不太明白 Boyer-Moore 将如何用于这项任务。 Boyer-Moore 是一种在字符串中查找子字符串的方法。

关于c++ - 用于查找多数元素的分而治之算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28957303/

amp多数sectioncountc++algorithm

有关c++ - 用于查找多数元素的分而治之算法？的更多相关文章

  1. ruby-on-rails - Rails 常用字符串(用于通知和错误信息等) - 2

    大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje

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

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

  3. Ruby Sinatra 配置用于生产和开发 - 2

    我已经在Sinatra上创建了应用程序，它代表了一个简单的API。我想在生产和开发上进行部署。我想在部署时选择，是开发还是生产，一些方法的逻辑应该改变，这取决于部署类型。是否有任何想法，如何完成以及解决此问题的一些示例。例子:我有代码get'/api/test'doreturn"Itisdev"end但是在部署到生产环境之后我想在运行/api/test之后看到ItisPROD如何实现？ 最佳答案 根据SinatraDocumentation:EnvironmentscanbesetthroughtheRACK_ENVenvironm

  4. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  5. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  6. ruby - inverse_of 是否适用于 has_many？ - 2

    当我使用has_one时，它​​工作得很好，但在has_many上却不行。在这里您可以看到object_id不同，因为它运行了另一个SQL来再次获取它。ruby-1.9.2-p290:001>e=Employee.create(name:'rafael',active:false)ruby-1.9.2-p290:002>b=Badge.create(number:1,employee:e)ruby-1.9.2-p290:003>a=Address.create(street:"123MarketSt",city:"SanDiego",employee:e)ruby-1.9.2-p290

  7. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  8. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  9. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  10. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

随机推荐