blocks|key|1390164|text|不确定分而治之的方法，但是数组/列表中的大多数元素可以在O(nlogn)时间内识别。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1390165|这可以使用使用结构的binary+search+tree来完成。|1390166|struct+tree
{
++int+element;
++int+count;
}BST;|code-block|syntax|javascript|1390167|算法|1390168|在BST中逐一插入元素，如果已经存在，则增加节点的计数。|ordered-list-item|1390169|在任何阶段，如果节点的计数超过n/2，则返回。|1390170|现在，最糟糕的情况复杂度可以是O(n%5E2)在倾斜BST的情况下。因此，使用self+balancing+BST确保O(nlogn)时间。|1390171|如果您想使用Divide和Conquer方法来完成它，|BOLD|1390172|算法：|1390173|将数组分为L和R两部分。|1390174|int+m1+=多数(L)；int+m2+=多数(R)；|1390175|如果m1是多数，则返回它。|1390176|如果m2是多数派，请重新修改它。|1390177|否则返回“无多数元素”。|1390178|代码：|1390179|i=0;j=arr.length；|1390180|int+majority(int+*A,+int+i,+int+j)
{
++++int+m1=+majority(A,+i,+j/2-1);
++++int+m2=+majority(A,+j/2%2B1,+j);
++++int+count+=+0;
++++for(int+i=0;+i<j;+i%2B%2B)
++++++++if(A[i]+==+m1)
++++++++++++count%2B%2B;
++++if(count+>+j/2)
++++++++return+m1;
++++count+=+0;
++++for(int+i=0;+i<j;+i%2B%2B)
++++++++if(A[i]+==+m2)
++++++++++++count%2B%2B;
++++if(count+>+j/2)
++++++++return+m2;
++++}
++++return+-1;
}|1390181|entityMap^0|S|8|0|A|I|0|0|0|1|3|0|F|3|0|F|6|11|I|1L|8|0|6|E|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1I|8|@$9|1J|A|1K|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1L|8|@$9|1M|A|1N|B|C]]|D|@]|E|$]]|$1|H|3|I|5|J|7|1O|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|1P|8|@]|D|@]|E|$]]|$1|O|3|P|5|Q|7|1Q|8|@$9|1R|A|1S|B|C]]|D|@]|E|$]]|$1|R|3|S|5|Q|7|1T|8|@$9|1U|A|1V|B|C]]|D|@]|E|$]]|$1|T|3|U|5|6|7|1W|8|@$9|1X|A|1Y|B|C]|$9|1Z|A|20|B|C]|$9|21|A|22|B|C]]|D|@]|E|$]]|$1|V|3|W|5|6|7|23|8|@$9|24|A|25|B|X]]|D|@]|E|$]]|$1|Y|3|Z|5|6|7|26|8|@]|D|@]|E|$]]|$1|10|3|11|5|Q|7|27|8|@]|D|@]|E|$]]|$1|12|3|13|5|Q|7|28|8|@]|D|@]|E|$]]|$1|14|3|15|5|Q|7|29|8|@]|D|@]|E|$]]|$1|16|3|17|5|Q|7|2A|8|@]|D|@]|E|$]]|$1|18|3|19|5|Q|7|2B|8|@]|D|@]|E|$]]|$1|1A|3|1B|5|6|7|2C|8|@]|D|@]|E|$]]|$1|1C|3|1D|5|6|7|2D|8|@]|D|@]|E|$]]|$1|1E|3|1F|5|J|7|2E|8|@]|D|@]|E|$K|L]]|$1|1G|3|-4|5|6|7|2F|8|@]|D|@]|E|$]]]|1H|$]]

Not sure about the divide and conquer approach, but majority element in an array/list can be identified in <code>O(nlogn)</code> time. 

This can be done using a <code>binary search tree</code> using structure

<pre><code>struct tree
{
 int element;
 int count;
}BST;
</code></pre>

Algorithm:

<ol>
<li>Insert elements in <code>BST</code> one by one and if already present then increment the count of the node. </li>
<li>At any stage, if count of a node becomes more than <code>n/2</code> then return.</li>
</ol>

Now, the worst case complexity can be <code>O(n^2)</code> in case of skewed BST. So, use a <code>self balancing BST</code> to ensure <code>O(nlogn)</code> time. 

If you want to do it using Divide and Conquer approach, 

Algorithm :

<ol>
<li>Divide array into two parts L and R.</li>
<li>int m1 = Majority(L); int m2 = Majority(R);</li>
<li>if m1 is majority return it.</li>
<li>if m2 is majority retun it. </li>
<li>Otherwise return "no majority element".</li>
</ol>

Code : 

i=0;j=arr.length;

<pre><code>int majority(int *A, int i, int j)
{
 int m1= majority(A, i, j/2-1);
 int m2= majority(A, j/2+1, j);
 int count = 0;
 for(int i=0; i&lt;j; i++)
 if(A[i] == m1)
 count++;
 if(count &gt; j/2)
 return m1;
 count = 0;
 for(int i=0; i&lt;j; i++)
 if(A[i] == m2)
 count++;
 if(count &gt; j/2)
 return m2;
 }
 return -1;
}
</code></pre>

blocks|key|309127|text|第一个问题是，您只返回一个基本情况下的值；其余时间，您将打印一个值并返回None。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|309128|第二，第一次递归调用是在i+==+0时进行的，这意味着L[i:len(L)]与L相同，因此您并没有明显减少问题的大小。至少，您需要for+i+in+range(1,+len(L))，但我怀疑您没有正确地将问题分解为子问题。(您不应该像建议的那样进行那么多的递归调用。)|309129|entityMap^0|10|4|0|C|6|R|B|13|1|1T|P|0^^$0|@$1|2|3|4|5|6|7|J|8|@$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|M|8|@$9|N|A|O|B|C]|$9|P|A|Q|B|C]|$9|R|A|S|B|C]|$9|T|A|U|B|C]]|D|@]|E|$]]|$1|H|3|-4|5|6|7|V|8|@]|D|@]|E|$]]]|I|$]]

Your first problem is that you are only returning a value in the base case; the rest of the time, you print a value and return <code>None</code>.

Second, the first recursive call is made when <code>i == 0</code>, which means <code>L[i:len(L)]</code> is the same as <code>L</code>, so you aren't acutually reducing the size of the problem. At the very least, you want <code>for i in range(1, len(L))</code>, but I suspect you aren't properly decomposing the problem into subproblems. (You shouldn't have to make as many recursive calls as you are proposing.)

blocks|key|309144|text|不知道你的算法是如何工作的，我的算法实现了使用分而治之技术寻找多数元素。它将数组分成两片，并检查潜在的候选对象。然后检查它是否是多数元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|309145|def+divideAndConquer(array):+#Function+to+solve+by+divide+and+conquer
++++if(len(array)==1):
++++++++return+array[0]
++++middle+=+len(array)//2
++++left+=+array[:middle]+#First+half
++++right+=+array[middle:]+#Second+half
++++cLeft+=+divideAndConquer(left)+#candidate+for+left+side
++++cRight+=+divideAndConquer(right)+#candidate+for+right+side
++++if+cLeft+==+cRight:+#if+both+have+the+same+candidate,+it+is+the+one
++++++++return+cLeft
++++if+array.count(cLeft)>middle:+#if+not,+check+in+left
++++++++return+cLeft
++++if+array.count(cRight)>middle:+#else+check+in+right
++++++++return+cRight
++++return+"No+majority+element"+#no+majority+element|code-block|syntax|javascript|309146|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Not sure how your algorithm works,
mine does the implementation of finding majority element using divide and conquer technique. It divides the array into two slices and checks for potential candidate. It is then checked that whether it is majority element or not.

<pre><code>def divideAndConquer(array): #Function to solve by divide and conquer
 if(len(array)==1):
 return array[0]
 middle = len(array)//2
 left = array[:middle] #First half
 right = array[middle:] #Second half
 cLeft = divideAndConquer(left) #candidate for left side
 cRight = divideAndConquer(right) #candidate for right side
 if cLeft == cRight: #if both have the same candidate, it is the one
 return cLeft
 if array.count(cLeft)&gt;middle: #if not, check in left
 return cLeft
 if array.count(cRight)&gt;middle: #else check in right
 return cRight
 return "No majority element" #no majority element
</code></pre>

<blockquote>
 <ol start="9">
 <li>(10 points) Write an O(nlogn) algorithm to find the majority element of a list of items. (Assume that the number of elements is a power of 2). Again, the only operation you can use on items of the list is equality comparison. Hint: solve a problem of size n by solving two sub-problems of size n/2</li>
 </ol>
</blockquote>

This was a test question on divide and conquer, for my algorithms class.
Here is the code I wrote in python 3.5.

<pre><code>def majElement(L):
 tally = 0
 if len(L) == 1:
 return 1
 for i in range(len(L)):
 tally = majElement(L[i:len(L)]) + majElement(L[len(L)/2:])

 if tally &gt; (len(L)/2):
 print(L[i])
</code></pre>

This code results in a stack overflow. Some how I'm not reaching my base case. 
How can I stop the infinite recursive calls?

Write an algorithm that returns the majority element in a list

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

(10分)编写一个O(nlogn)算法来查找项目列表中的大多数元素。(假设元素数为2的幂)。同样，对列表中的项可以使用的唯一操作是相等比较。提示:通过解决n/2大小的两个子问题来解决n个大小的问题。对于我的演算法课来说，这是一个关于分而治之的试题。下面是我用python3.5编写的代码。def majElement(L...

问编写返回列表中多数元素的算法
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问编写返回列表中多数元素的算法EN