计算隐藏数组模式的高效算法
Efficient algorithm to calculate the mode of a hidden array
我正在尝试解决我在问题中描述的问题的扩展：
对于此扩展，已知有 3 个派对的代表参加活动，并且参加派对的 1 个派对的成员比其他任何派对的成员都多。可以在下面找到问题的正式描述。
给你一个整数n。有一个大小为 n 的隐藏数组 A，其中包含的元素可以取 3 个值中的 1 个。有一个值，设它是 m，它在数组中出现的频率比其他 2 个值高。
您可以查询 introduce(i, j) 形式，其中 i≠j，且 1 <= i, j <= n，您将在 return 中得到一个布尔值：您将返回 1，如果 A[i] = A[j]，否则为 0。
输出：B ⊆ [1, 2. ... n] 其中 B 中每个元素的 A 值为 m.
对此的强力解决方案可以在 O(n2) 中计算 B，方法是在 n(n-1) 种元素组合上调用 introduce(i, j) 和创建 3 个包含元素 A 索引的列表，当对其调用 introduce 时，returned 为 1，returning 最大列表。
我理解 Boyer–Moore majority vote algorithm 但找不到针对此问题修改它的方法或找到解决它的有效算法。
扫描所有 A[i] = A[0]，并为所有满足 A[i] != A[0] 的 i 制作列表 I[]。然后扫描所有 A[I[j]] = A[I[0]]，依此类推。这需要对 A[] 中的每个可能值进行一次 O(n) 扫描。
[我假设如果 introduce(i, j) = 1 和 introduce(j, k) = 1, 那么 introduce(i, k) = 1 -- 所以你不需要检查元素的所有组合。]
当然，这并没有告诉你 'm' 是什么，它只是列出 n，其中 n是值的个数，每个list都是A[i]相同的'i'。
我正在尝试解决我在问题中描述的问题的扩展：
对于此扩展，已知有 3 个派对的代表参加活动，并且参加派对的 1 个派对的成员比其他任何派对的成员都多。可以在下面找到问题的正式描述。
给你一个整数n。有一个大小为 n 的隐藏数组 A，其中包含的元素可以取 3 个值中的 1 个。有一个值，设它是 m，它在数组中出现的频率比其他 2 个值高。
您可以查询 introduce(i, j) 形式，其中 i≠j，且 1 <= i, j <= n，您将在 return 中得到一个布尔值：您将返回 1，如果 A[i] = A[j]，否则为 0。
输出：B ⊆ [1, 2. ... n] 其中 B 中每个元素的 A 值为 m.
对此的强力解决方案可以在 O(n2) 中计算 B，方法是在 n(n-1) 种元素组合上调用 introduce(i, j) 和创建 3 个包含元素 A 索引的列表，当对其调用 introduce 时，returned 为 1，returning 最大列表。
我理解 Boyer–Moore majority vote algorithm 但找不到针对此问题修改它的方法或找到解决它的有效算法。
扫描所有 A[i] = A[0]，并为所有满足 A[i] != A[0] 的 i 制作列表 I[]。然后扫描所有 A[I[j]] = A[I[0]]，依此类推。这需要对 A[] 中的每个可能值进行一次 O(n) 扫描。
[我假设如果 introduce(i, j) = 1 和 introduce(j, k) = 1, 那么 introduce(i, k) = 1 -- 所以你不需要检查元素的所有组合。]
当然，这并没有告诉你 'm' 是什么，它只是列出 n，其中 n是值的个数，每个list都是A[i]相同的'i'。