查找无序排列的主导模式 [英] Find dominant mode of an unsorted array

问题描述

请注意，这是一个家庭作业。

Note, this is a homework assignment.

我需要找到一个数组的方式（正值），其次返回值，如果模式是大于的sizeof（阵列）/ 2 ，占主导地位的价值。有些阵列将既没有。 那是很简单的，但有使阵列必须不会被之前的确定排序约束，另外地，复杂性必须是O（nlogn）的数量级上。

I need to find the mode of an array (positive values) and secondarily return that value if the mode is greater that sizeof(array)/2,the dominant value. Some arrays will have neither. That is simple enough, but there is a constraint that the array must NOT be sorted prior to the determination, additionally, the complexity must be on the order of O(nlogn).

使用这个第二个制约因素，以及主定理我们可以确定的时间复杂度'T （N）= A * T（N / B）+ N ^ D'其中A = B和log_B（A）= D为O（nlogn）是真实的。因此，A = B = D = 2。这也是方便的，因为主要的值必须是占优势的第一，第二，或阵列的两半。

Using this second constraint, and the master theorem we can determine that the time complexity 'T(n) = A*T(n/B) + n^D' where A=B and log_B(A)=D for O(nlogn) to be true. Thus, A=B=D=2. This is also convenient since the dominant value must be dominant in the 1st, 2nd, or both halves of an array.

使用'T（N）= A * T（N / B）+ N ^ D'，我们知道，搜索功能将调用自己两次在每个级别（A），划分问题，通过2设定在每个级别（ B）。我被困在找出如何让我的算法，考虑到在每个级别的N ^ 2。

Using 'T(n) = A*T(n/B) + n^D' we know that the search function will call itself twice at each level (A), divide the problem set by 2 at each level (B). I'm stuck figuring out how to make my algorithm take into account the n^2 at each level.

为使这方面的一些code：

To make some code of this:

int search(a,b) {
    search(a, a+(b-a)/2);
    search(a+(b-a)/2+1, b);
}

胶水我很想念这里是如何结合这些划分的功能，我认为这将实施第n ^ 2的复杂性。有一些诀窍这里，其中占主导地位的一定是占主导地位的第一或第二个半或两个，不太清楚如何帮助我，现在具有的复杂性约束。

The "glue" I'm missing here is how to combine these divided functions and I think that will implement the n^2 complexity. There is some trick here where the dominant must be the dominant in the 1st or 2nd half or both, not quite sure how that helps me right now with the complexity constraint.

我写下来的小阵列的一些例子，我已经拉出方面，它会分裂。我似乎不能去找到一个，那总是返回主导价值单一方法的正确方向。

I've written down some examples of small arrays and I've drawn out ways it would divide. I can't seem to go in the correct direction of finding one, single method that will always return the dominant value.

在0级，函数需要调用自己要搜索的前半部分和后半部分的阵列。需要递归，并调用自身。然后在每一个级别，它需要执行N ^ 2的操作。因此，在一个数组[2,0,2,0,2]，将拆分成上[2,0]搜索，并在[2,0,2]搜索，并执行25操作。在[2,0]一个搜索会叫上[2]搜索，并在[0]搜索，并进行4的操作。我假设这将需要一个搜索阵列空间本身。我正打算用C ++和使用的东西，从STL迭代和计数的值。我可以创建一个大阵，只是更新计数他们的索引。

At level 0, the function needs to call itself to search the first half and second half of the array. That needs to recurse, and call itself. Then at each level, it needs to perform n^2 operations. So in an array [2,0,2,0,2] it would split that into a search on [2,0] and a search on [2,0,2] AND perform 25 operations. A search on [2,0] would call a search on [2] and a search on [0] AND perform 4 operations. I'm assuming these would need to be a search of the array space itself. I was planning to use C++ and use something from STL to iterate and count the values. I could create a large array and just update counts by their index.

推荐答案

如果你想找到一个数组的只是主导模式，并做到这一点递归，这里的伪code：

If you want to find just the dominant mode of an array, and do it recursively, here's the pseudo-code:

def DominantMode(array):
    # if there is only one element, that's the dominant mode
    if len(array) == 1: return array[0]
    # otherwise, find the dominant mode of the left and right halves
    left = DominantMode(array[0:len(array)/2])
    right = DominantMode(array[len(array)/2:len(array)])
    # if both sides have the same dominant mode, the whole array has that mode
    if left == right: return left
    # otherwise, we have to scan the whole array to determine which one wins
    leftCount = sum(element == left for element in array)
    rightCount = sum(element == right for element in array)
    if leftCount > len(array) / 2: return left
    if rightCount > len(array) / 2: return right
    # if neither wins, just return None
    return None

上面的算法是O（nlogn）的时间，但只有O（LOGN）的空间。

The above algorithm is O(nlogn) time but only O(logn) space.

。可以通过存储historgram，所述元件值映射到其频率哈希表为O（n）的时间（访问数组的每个元素恰好一次）执行此操作。

If you want to find the mode of an array (not just the dominant mode), first compute the histogram. You can do this in O(n) time (visiting each element of the array exactly once) by storing the historgram in a hash table that maps the element value to its frequency.

在柱状图已经被计算，可以遍历它（访问每个元素最多一次）找到最高频率。一旦你找到一个频率比数组的一半大小，您可以立即返回，而忽略了直方图的其余部分。因为直方图的大小可以不大于原数组的大小大，这一步也为O（n）的时间（和O（n）的空间）。

Once the histogram has been computed, you can iterate over it (visiting each element at most once) to find the highest frequency. Once you find a frequency larger than half the size of the array, you can return immediately and ignore the rest of the histogram. Since the size of the histogram can be no larger than the size of the original array, this step is also O(n) time (and O(n) space).

由于这两个步骤是O（n）的时间，由此产生的算法复杂度为O（n）的时间。

Since both steps are O(n) time, the resulting algorithmic complexity is O(n) time.

这篇关于查找无序排列的主导模式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！