10

例如，数组的答案：

1、11、3、95、23、8、1

将是 1，因为所有其他元素只出现一次，而 1 出现两次。

我在 stackoverflow 上看到的许多与此问题类似的问题都要求找到绝对多数（答案在长度为 n 的数组中至少出现 n/2），或者使用排序或哈希表回答问题。前者不是我要的，后者要么太慢（ O(n log n) 用于排序），要么使用太多内存（ O(n) 用于哈希表）。

这样的算法存在吗？如果不是，是否有证据表明为什么这是不可能的？包括一个来源会很好。

4

4 回答 4

1

使用这里的想法：

我们如何在 O(n) 时间和 O(1) 空间复杂度内找到数组中的重复数

并应用类似于计数排序的技术。也就是说，创建 N 个 bin（一个大小为 N 的数组），其中 N 是您期望遇到的最大整数。这仍然是 O(1) 空间。然后，在 O(n) 时间内遍历原始数组，当遇到值i时，将索引i处的结果数组增加1。然后，遍历结果数组（再次 O(1) 时间），找到最大单值。该值的索引将是原始列表中最常见的值。

于 2012-08-02T17:47:27.120 回答
1

这不是一个完整的答案，但它应该有助于阐明为什么这个问题很困难。

考虑我们想要设计一种算法，它对数组进行一次扫描（以某种顺序）以找到最常见的元素。在我们的算法运行期间，允许保留一些数据结构S。让我们看看 中有多少信息S，因此我们是否可以将它包含在O(1)内存中。

假设我们的算法已经处理k了数组的第一个元素。现在S可以告诉我们范围内最常见的元素a[0..k]。但是，假设我们知道k+1'st 元素，那么我们也会知道 range 中最常见的元素a[0..k+1]。如果不能，如果n是，我们的算法将无法工作k+1。更一般地说，给定元素a[k..m]和的知识S，我们知道 中最常见的元素a[0..m]。

我们可以使用上述参数从 中提取信息S。假设我们正在使用范围内的整数[0,u]（如果原始数组占用空间，则必须有一些范围O(n)）。如果最初最常见的元素是5，那么我们添加0'，直到最常见的元素发生变化。如果取c零，a[0..k]则必须包含比'c更多的'。重复这个论点，我们得到了很多线性方程，我们可以求解这些方程来准确判断每个元素在 中出现的次数。50[0,u]a[0..k]

这告诉我们，任何进行扫描的数据结构都可能存储所有可见元素的计数（以某种压缩方式）。如果您对数学感兴趣，那么看到n数字后存储的就是将无法区分的项目划分为可区分的箱log(n+u-1 choose n)的方式数量的日志。这还不止。nulog(u^n/n!) >= nlogu-nlogn

结论：任何只执行一次数组传递的算法都必须使用尽可能多的内存来存储到目前为止看到的所有计数。如果n比较小，u则对应于存储n字的内存。

（好吧，我们也可以覆盖现有的数组，而不是额外的内存）。

这里还有很多值得探索的地方。例如，多次传递如何影响上述参数。但是我认为我应该在这一点上停下来:)，但在我看来，任何具有大的线性时间算法都不太可能u摆脱O(1)额外的内存。

于 2014-11-16T00:37:48.633 回答
1

如果你想有固定的空间来找到最常见的元素，你需要有一个元素的最大位数。如果您不这样做，那么大型输入数组可能具有更大的输入数字，以便表示数字的位大于您存储结果的固定空间。

假设k是您支持的最大数的长度。如果您尝试天真地创建一个2^k桶数组来计算每个数字的出现次数（计数器排序），您可能会收到一个由相同数字组成的数组，在这种情况下，您的算法最终需要log(n)空间来存储总和。[*]

如果我们看一个更简单的问题版本 - 确定输入中是否有更多1' 或0' ，我认为您需要一个堆栈来执行此操作（您存储多少1或0领先），因此是恒定的空间是不可能的，即使我们将输入长度限制为k = 1位大小。

您的问题更普遍（k > 1，但仍然是固定的），并且还需要非常量的空间，所以这是不可能的，因为问题的措辞。

[*] 如果您假设计数器具有O(1)空间复杂性，那么您可以采用计数器排序方法，尽管这样做您已经为输入数组的最大大小设置了一个上限（这可能是也可能不是可接受的）：就 而言k，数组的输入元素的c最大位数以及计数器中的最大位数，您的数组最多可以包含2^k * 2^c元素（其中一个计数器会在下一个元素上溢出）。为了解决这个问题，您可以添加一个O(1)时间步来减少您的计数器，以便如果所有计数器都不是，则最小值总是0在处理每个元素之后0，从而使它们相对而不是绝对。这需要O(1)时间，因为如果所有元素都不为零，则只需要在每个元素上执行它时递减O(2^k) = O(1)计数器。1虽然该算法现在可以处理一些任意大的输入，但任何具有子数组的输入数组都有两个值a，并且对于某些输入b，count(a) - count(b) > 2^c = max(counter)使用计数器策略将失败。事实上，依赖O(1)空间复杂度计数器方法的结果是，所有以相同元素开头的数组2^c + 1都不能由该算法处理。

于 2016-04-09T12:17:35.930 回答
-2

这是我读取数组中最常见元素的脚本

<?php

class TestClass {

    public $keyVal;
    public $keyPlace = 0;

    //put your code here
    public function maxused_num($array) {
        $temp = array();
        $tempval = array();
        $r = 0;
        for ($i = 0; $i <= count($array) - 1; $i++) {
            $r = 0;
            for ($j = 0; $j <= count($array) - 1; $j++) {
                if ($array[$i] == $array[$j]) {
                    $r = $r + 1;
                }
            }
            $tempval[$i] = $r;
            $temp[$i] = $array[$i];
        }
        //fetch max value
        $max = 0;
        for ($i = 0; $i <= count($tempval) - 1; $i++) {
            if ($tempval[$i] > $max) {
                $max = $tempval[$i];
            }
        }
        //get value 
        for ($i = 0; $i <= count($tempval) - 1; $i++) {
            if ($tempval[$i] == $max) {
                $this->keyVal = $tempval[$i];
                $this->keyPlace = $i;
                break;
            }
        }

        // 1.place holder on array $this->keyPlace;
        // 2.number of reapeats $this->keyVal;
        return $array[$this->keyPlace];
    }

}

$catch = new TestClass();
$array = array(1, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 3, 1, 2, 3, 1, 1, 2, 5, 7, 1, 9, 0, 11, 22, 1, 1, 22, 22, 35, 66, 1, 1, 1);
echo $catch->maxused_num($array);
于 2016-04-09T12:00:26.517 回答