4

首先，这不是一个家庭作业或类似的东西，这是我最后一个问题Candidate in find major element in an array 中的一个暗示性问题。

对象有O 1 , O 2 , ..., O n的n 种类，还有一个数组，是Oi的个数（即有O i s，数组给定），每一个> 。F[1...n]F[i]F[i]F[1...n]F[i]0

现在使用以下规则来配对对象：

如果i != j，O i可以与 O j配对，
否则如果i == j，O i不能与 O j配对。

即，只有两种不同类型的对象可以相互配对。

  1. 输入数组是否存在有效的配对方法F[1...n]？给出一个时间复杂度最好的算法来判断真假并证明其正确性。

  2. 如果存在，则输出一个有效的配对序列。给出你的算法和时间/空间复杂度分析。

例如， 输入 F[] = {10, 2, 4, 4};

那么至少存在一种有效的配对方法：

2 O 1 s 和 2 O 2 s 配对，4 O 1 s 和 4 O 3 s 配对，4 O 1 s 和 4 O 4 s 配对。

一种有效的配对顺序是：

(1,2) (1,2) (1,3) (1,3) (1,3) (1,3) (1,4) (1,4) (1,4) (1,4)

4

2 回答 2

5

检查 O(n) 中是否存在解决方案

设s为 的总和F。

  • 如果s是奇数，则没有解决方案（直观）
  • 如果存在没有解决方案的情况（直观i）F[i] > s/2
  • 否则，存在解决方案（以下是构造证明）

在 O(n) 中找到解决方案

# Find s
s = 0
for i in 1..n:
    s += F[i]

# Find m such that F[m] is maximal
m = 1
for i in 1..n:
    if F[i] > F[m]:
         m = i

if s % 2 != 0 or F[m] > s/2:
    fail

a = 1
b = 1

# Pair off arbitrary objects (except those of type m) until F[m] = s/2    
while s/2 > F[m]:
    # Find a type with a non-zero frequency
    until F[a] > 0 and a != m:
        a = a + 1
    # Find another type with a non-zero frequency
    until F[b] > 0 and b != m and b != a:
        b = b + 1

    count = min(F[a], F[b], s/2 - F[m])
    pair(a, b, count)

# Pair off objects of type m with objects of different types
while F[m] > 0:
    # Find a type with a non-zero frequency
    until F[a] > 0 and a != m:
        a = a + 1
    pair(a, m, F[a])

end of algorithm

def pair(a, b, count):
    # Pairs off 'count' pairs of types a and b
    F[a] = F[a] - count
    F[b] = F[b] - count
    s = s - (2 * count)
    output "Pairing off $a and $b ($count times)"

这两个while循环都是线性的。第一个 while 循环在每次迭代时增加一个a或b至少一个，因为在匹配count对之后，要么F[a]为零，要么F[b]为零，要么s/2 = F[m]循环终止。a并且b可以在n访问所有元素之前每次递增。第二个 while 循环也是线性的，因为它a在每次迭代期间至少递增 1。

关键不变量是
(1) F[m]是F
(2) F[m] <= s/2
的最大元素， 我认为两者在检查时都相当明显。

使用内部循环，只要s/2 > F[m]必须至少有两个非零频率的其他对象类型。如果只有一个，比如说a，那么
F[a] + F[m] = s
F[a] = s - F[m] > s - s/2（从循环条件）
F[a] > s/2
F[a] > F[m]
这是不变量(1)的矛盾。

由于至少有两种具有非零频率的类型（除了m），循环将能够找到类型a并b配对对象直到s/2 = F[m]。

第二个循环是微不足道的。由于恰好有一半的对象是 type m，因此每个 type 对象m都可以与不同类型的对象配对。

于 2013-04-19T06:17:47.170 回答
1

这是一个建议。不过，我不确定它是否适用于所有可能的情况，或者它是否是最有效的算法。

设为n索引的总数。构造对象类型数量的最高值优先级队列，其中每个对象类型是它的索引i。换句话说，创建一个优先队列，其中队列中的排序值是 的值F。将每个节点与该类型的所有对象的列表相关联。这需要O(n log(n))时间。

对于每种对象类型，从具有最多重复项的类型开始，然后到具有最少重复项的类型，将该对象“类”中的一个对象与仍然有对象的其他每个类的一个对象配对，并从队列中的该节点中删除该对象。由于除了顶部的每个队列项都会少一个对象，因此大部分队列仍将按优先级队列顺序排列；然而，顶部节点将有n-1更少的项目（或者它将是空的），因此向下堆以维护队列。此外，删除没有剩余对象的节点。使用新的最高队列值重复此过程，直到所有节点都配对。这需要O(n log(n) + k)时间，k项目总数在哪里。假设k显着大于n，总时间复杂度为O(k)。

同样，我不太确定如果可能的话，这是否总能找到解决方案。我的直觉是，如果您在每次配对后重新堆放（如有必要），您将确保如果可以找到完整配对，但（1）效率会低得多，并且（2）我'我不确定原始算法不会在哪些情况下成功，并且（3）我不完全确定即使每次都能奏效。

至于哪些值F没有解，显然如果存在一类对象的元素比所有其他类组合的元素多，则不可能配对。除此之外......我不太确定。调查我的“改进”算法是否正确评估每个案例会很有趣。

于 2013-04-19T05:58:30.413 回答