3

我正在尝试解决这个问题：https ://www.interviewstreet.com/challenges/dashboard/#problem/4f9a33ec1b8ea

假设 A 是 n 个数字 (A1, A2, A3, ... , An) 的列表，B (B1, B2, B3, ..., Bn) 是这些数字的排列。我们说 B 是 K 操作的当且仅当它的以下值：

M(B) = min( B1 Xor B2, B2 Xor B3, B3 Xor B4, ... , Bn-1 Xor Bn, Bn Xor B1 ) 不小于 2^K。给你 n 个 A1 到 An，你必须找到最大的 K 使得这些数字的排列 B 是 K 操纵的。

输入：

在输入的第一行有一个整数 N。在输入的第二行有 N 个整数 A1 到 An N 不超过 100。Ai 是非负数，适合 32 位整数。

输出：

在输出中打印一个整数作为测试的答案。如果没有这样的 K 打印 -1 到输出。

样本输入

3 13 3 10

样本输出

2

样本输入

4 1 2 3 4

样本输出

1

解释

第一个样本测试 这里列表 A 是 {13, 3, 10}。A 的一种可能排列是，B = (10, 3, 13)。

对于 B，min( B1 xor B2, B2 xor B3, B3 xor B1 ) = min( 10 xor 3, 3 xor 13, 13 xor 10 ) = min( 9, 14, 7 ) = 7。

所以存在 A 的置换 B 使得 M(B) 不小于 4 即 2^2。然而，不存在 A 的任何排列 B 使得 M(B) 不小于 8 即 2^3。所以 K 的最大可能值为 2。

==================================================== =================================

这是我迄今为止所做的尝试。

尝试 1：贪心算法

  1. 将输入放入数组 A[1..n]
  2. 计算值 M(A)。这给出了最小异或值的位置 (i, (i + 1) % n)
  3. 检查将 A[i] 或 A[(i + 1) % n] 与数组的任何其他元素交换是否会增加 M(A) 的值。如果存在这样的元素，请进行交换。
  4. 重复步骤 2 和 3，直到 M(A) 值无法提高。

这肯定给出了一个局部最大值，但我不确定这是否给出了全局最大值。

尝试 2：在给定邻居约束的情况下检查置换是否存在

  1. 给定输入 A[1..n]，对于 i = 1..n 和 j = (i+1)..n 计算 x_ij = A[i] XOR A[j]
  2. 计算最大值（x_ij）。请注意，对于某些 p，2^p <= max(x_ij) < 2^(p+1)。
  3. 收集所有 x_ij 使得 x_ij >= 2^p。请注意，此集合可以视为具有节点 {1, 2, .. n} 的图 G，如果 x_ij >= 2^p，则节点 i 和 j 在它们之间具有无向边。
  4. 检查图 G 是否有一个循环恰好访问每个节点一次。如果存在这样的循环，则 k = p。否则，令 p = p - 1，转到步骤 3。

这给出了正确的答案，但请注意，在第 4 步中，我们实质上是在检查一个图是否具有哈密顿循环，这是一个非常困难的问题。

有什么提示或建议吗？

4

3 回答 3

3

无需深入研究图论就可以解决这个问题。

关键推断

, 建议的性质rich是解决这个问题的关键：

跟进我的评论：B1 Xor B2 < 2^K 当且仅当 B1 和 B2 同意除 K 低位之外的所有位

基于上述性质，我们只需要找到n/2每个 A[i] 的每个唯一高阶位最多出现的最高 k。

换句话说，在一组值A[i] >> k中，如果每个值在大多数情况下重复n/2，则存在与 的 k 操作排列all the XOR values >= (2^k)。

为什么 n/2

假设如果您确实有多个n/2唯一的高阶位出现，则不可能获得置换 B，所有循环 XOR 均非零，即至少有一个B[i] XOR B[(i+1) % N]具有所有高阶位变为零，因此使M(B) < 2^k

伪代码

k = -1
for (bit = (MAX_BITS - 1) to 0) {
    HashMap count
    for (i = 0 to N - 1) {
        higherOrderVal = A[i] >> bit
        if (higherOrderVal exists in count) {
            count[higherOrderVal] += 1
        }
        else {
            count[higherOrderVal] = 1
        }
    }

    isValid = true
    for (element in count) {
        if (element > N/2) {
            isValid = false
            break
        }
    }
    if (isValid) {
        k = bit
        break
    }
}

O(M * N)此解决方案的时间复杂度是M表示用于表示数字（32 位、64 位等）的最大位数的常数因子，并且N是输入数组 A 的大小。

于 2015-03-15T04:35:10.520 回答
2

跟进我的评论：B1 Xor B2 < 2^K 当且仅当 B1 和 B2 同意除 K 个低位之外的所有位，因此 G 具有非常特殊的结构，即完全多部分，分区标签由除K 个低位。当且仅当不存在多数分割时，完整的多部图是哈密顿图。将此事实插入尝试 2。

于 2012-06-22T23:27:58.670 回答
0

贪婪方法#priority_queue

首先插入所有对 xor 值和连续索引 i 和 j ->pq.push(tuple(v[i]^v[j],i,j)) 现在弹出第一个 maxm xor 值并设置索引 i 和 j现在再次弹出来自 i 或 j 的 maxm xor 值，此操作最多执行 1 到 n 然后返回第 n 个弹出的 xor 值

于 2020-05-28T15:18:57.997 回答