-1

请注意，这是家庭作业。

我需要找到数组的模式（正值），然后如果模式大于sizeof(array)/2主导值，则返回该值。有些阵列两者都没有。这很简单，但是有一个约束条件是在确定之前不能对数组进行排序，此外，复杂度必须在 O(nlogn) 的数量级上。

使用第二个约束和主定理，我们可以确定时间复杂度 'T(n) = A*T(n/B) + n^D' 其中 A=B 和 log_B(A)=D 对于 O(nlogn ） 是真实的。因此，A=B=D=2。这也很方便，因为主导值必须在数组的第一、第二或两半中占主导地位。

使用 'T(n) = A*T(n/B) + n^D' 我们知道搜索函数将在每个级别 (A) 调用自身两次，在每个级别 (B) 将问题集除以 2。我一直在弄清楚如何让我的算法考虑到每个级别的 n^2。

制作一些代码：

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

我在这里缺少的“胶水”是如何组合这些划分的功能，我认为这将实现 n^2 复杂性。这里有一些技巧，其中主导必须是第一或第二半或两者中的主导，不太确定这如何帮助我现在解决复杂性约束。

我已经写下了一些小数组的例子，并且我已经画出了它的划分方式。我似乎无法找到一个始终返回主导值的单一方法的正确方向。

在级别 0，函数需要调用自身来搜索数组的前半部分和后半部分。这需要递归，并调用自己。然后在每一层，它需要执行 n^2 次操作。因此，在数组 [2,0,2,0,2] 中，它会将其拆分为对 [2,0] 的搜索和对 [2,0,2] 的搜索并执行 25 次操作。在 [2,0] 上的搜索将调用在 [2] 上的搜索和在 [0] 上的搜索并执行 4 次操作。我假设这些需要搜索数组空间本身。我打算使用 C++ 并使用 STL 中的东西来迭代和计算值。我可以创建一个大数组，并通过它们的索引更新计数。

4

2 回答 2

2

如果某个数字出现超过一半，则可以通过 O(n) 时间复杂度和 O(1) 空间复杂度来完成，如下所示：

int num = a[0], occ = 1;
for (int i=1; i<n; i++) {
    if (a[i] == num) occ++;
    else {
        occ--;
        if (occ < 0) {
            num = a[i];
            occ = 1;
        }
    }
}

由于您不确定是否出现这样的数字，您需要做的就是先应用上述算法得到一个数字，然后第二次迭代整个数组以获取该数字的出现并检查它是否大于一半。

于 2013-02-07T06:20:00.743 回答
2

如果你只想找到一个数组的主要模式，并递归地做，这里是伪代码：

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) 空间。

如果你想找到一个数组的模式（不仅仅是主模式），首先计算直方图。通过将直方图存储在将元素值映射到其频率的哈希表中，您可以在 O(n) 时间内完成此操作（仅访问数组的每个元素一次）。

计算出直方图后，您可以对其进行迭代（最多访问每个元素一次）以找到最高频率。一旦发现频率大于数组大小的一半，您可以立即返回并忽略直方图的其余部分。由于直方图的大小不能大于原始数组的大小，所以这一步也是O(n)时间（和O(n)空间）。

由于这两个步骤都是 O(n) 时间，因此产生的算法复杂度是 O(n) 时间。

于 2013-02-07T05:32:35.733 回答