2

给定一个非常大的整数数组，其中元素可以达到 10^9，我如何找到具有最大 AND 值的对。我目前的方法是计算所有可能的对并遍历它并找到最大值，但是它非常慢。还有其他方法吗？

4

2 回答 2

7

只要您可以找到至少两个具有相同最高有效位集的数字，解决方案将涉及其中两个。

接下来，丢弃所有其他元素并删除此 MSB 剩下的所有未丢弃数字并解决相同的问题。直到您只剩下两个数字或无事可做。

例如：

 input  || first iteration | second iteration
=================================================================
1110010 ||       x         |        x
0110111 ||   discarded     |    discarded        
1000000 ||       x         |    discarded
1000010 ||       x         |        x
=================================================================
=> solution: first and last

这是O(n log max_element).

于 2015-02-04T15:22:08.883 回答
0

查看两个连续数字 n - 1 和 n 的位模式不同的第一个位置。片刻思考表明，对于 n，该位必须为 1，对于 n - 1，该位必须为 0。否则不能。在那个位的左边，一切都是平等的，在那个位的右边，两者中较大的只有 0，较小的只有 1。它不可能是其他的。

因此我们有：

n           -> (common prefix) 1 0*
n - 1       -> (common prefix) 0 1*
-----------------------------------
n & (n - 1) -> (common prefix) 0 0*

例子：

88          -> 101 1 000
87          -> 101 0 111
------------------------
88 & 87     -> 101 0 000

共享前缀可以为空，带有重复位的星号尾部（0* 和 1* 的东西）可以为空。

尾巴总是全为零，所以如果它存在，那么 (n - 1) & (n - 2) 必须大于 n & (n - 1)，因为 (n - 1) 在那个地方全是 1 并且 ( n - 2) 只缺少最后一位。它还必须大于 n 范围内的所有其他 AND 对。

如果尾巴不存在——也就是说，如果 n 是奇数——那么 n & (n - 1) 在 n 之前的整个范围内具有最大 AND 值。如果不明显：“尾巴存在”的另一种表达方式是“n 是偶数”。

需要特殊处理的一种情况是 B = A + 1，即如果范围具有最短的可能长度。在这种情况下，如果 B 是偶数，则没有 (B - 2) 可以依靠。

因此，对于 A < B 的范围 [A, B] 的最大 AND 的计算变为：

if ((B & 1) == 1 || A > B - 2)
    return B & (B - 1);
else
    return (B - 1) & (B - 2);

对于完整的 Monty，请查看我在 HackerEarth提交的内容。

只有在发布答案后，我才发现本主题中讨论的问题与 HackerEarth 中的Maximum AND略有不同，因为处理是针对给定的输入向量而不是连续的数字范围进行的。

如果在排序序列的向下扫描期间发现合适的连续值，上述方案仍然可以提供提前退出条件，但这种情况有用的可能性可以忽略不计。

这是一个函数，可以通过从末尾向后扫描来识别排序序列中的最高共享位。它通常只需要扫描很少的元素就可以完成。由于不可能在不共享任何位的情况下选择最多 B 位的 B + 1 个值，因此该函数必须通过仅检查其上端的对数少数值来找到已排序序列的共享高位。

static int common_high_bit (int[] v, int lo, int hi)
{
    int shared = 0;

    for (int seen = 0, i = hi - 1; i >= lo && v[i] >= shared; --i)
    {
        int m = shared | seen & v[i];

        if (m > shared)  // discovered a higher shared bit
        {
            m |= m >>  1;
            m |= m >>  2;
            m |= m >>  4;
            m |= m >>  8;
            m |= m >> 16;

            shared = m;
        }

        seen |= v[i];
    }

    return shared - (shared >> 1);
}

不过，没有必要对整个序列进行排序。执行堆排序的“heapify”步骤（可以在 O(n) 中完成）就足够了，然后一个一个地提取最大值并将它们输入到上述算法中，直到它退出或输入用尽。

一旦识别出高位，需要从序列中提取具有该位集的所有值，位 k 及其左侧的所有内容都归零，并且结果经过相同的处理。一旦候选集缩小到可管理的大小，简单的二次算法就可以比大型机器更有效地处理其余部分。

注意：共享的高位不一定是 IVlad 的答案所暗示的 MSB。例如考虑：

101xxxxx
 11xxxxx

可以看出，最高共享位不是任何一个数字的 MSB。

出于类似的原因，在屏蔽掉共享高位及其剩余部分后，我们不能对剩余候选集中的值顺序做出太多假设。

然而，情况并不黯淡，因为异常的、不方便的星座不可能很多，一旦我们在序列中下降到共享高位是那里的值的 MSB 时，只需要从对数上提取更多的值它完成了下一步的候选集。

于 2016-07-13T17:36:34.870 回答