相关疑难解决方法(0)

您将获得一个32位无符号整数数组,其长度最大为2 ³²,其中包含数组中一半以上条目的属性等于N,对于某些32位无符号整数N.查找N查看每个数字在数组中只使用一次并使用最多2 kB的内存.

您的解决方案必须是确定性的,并保证找到N.

我想在这里讨论一个我在数据结构书中找到的算法.本书提供了算法的草图,以便在大小为N的数组中找到多数元素(出现多于N/2).算法草图如下:

首先,找到候选多数元素(这是更难的部分).这个候选人是唯一可能成为多数元素的元素.第二步确定这个候选人是否实际上是多数.这只是对数组的顺序搜索.要在数组中找到候选项A,形成第二个数组B.然后比较A1,A2.如果它们相等,则将其中一个添加到B; 否则什么也不做.然后比较A3和A4.如果它们相等,再将其中一个添加到B; 否则什么也不做.以这种方式继续,直到读取整个数组.然后递归地找到B的候选者; 这是A的候选人.

我想出如果N是偶数,算法工作正常.但如果N是奇数怎么办？我们如何处理这个案子？

我在一次采访中被要求给出一个O(n)算法来打印一个在数组中出现超过n/2次的元素,如果有这样的元素的话.n是数组的大小.我对如何做到这一点没有任何线索.有人可以帮忙吗？

您有一个已知大小为 n 的数组或键列表。未知此列表中有多少个唯一键，可能少至 0，多至 n。这些键没有特定的顺序，而且实际上也不可能如此，因为这些键没有大于或小于的概念，只有相等或不等的概念。现在，在你说哈希映射之前，我认为还有一个条件会影响这个想法：每个键的值都是私有的。您可以获得的有关该密钥的唯一信息是它是否与另一个密钥相同。所以基本上：

class key{
    private:
        T data;
        ...
    public:
        ...
        bool operator==(const key &k){return data==k.data}
        bool operator!=(const key &k){return data!=k.data}
};

key array[n];

现在，有没有一种算法可以在线性时间内判断数组中超过一半的键是否是相同的键？如果不是，O(n*log(n)) 又如何呢？例如，假设数组只有 3 个唯一键。数组的 60% 填充有 key.data==foo、30% key.data==bar 和 10% key.data==derp 的键。该算法只需要确定超过 50% 的键属于同一类型（data==foo 的键），并返回这些键之一。

根据我的教授的说法，这可以在 O(n) 时间内完成，但他说我们只需要找到一个可以在 O(n*log(n)) 时间内完成的任务。