arrays - 所有对象都可以按顺序配对吗？

Question

首先，这不是作业或类似的东西，这是我上一个问题的暗示性问题Candidate in finding majority element in an array .

有 n 种 种对象 O₁, O₂, ..., O_n，还有一个数组F[1...n]，F[i]是Oi的个数(即有F[i] O_is, array F[1...n] is given), and every F[i] > 0 .

现在使用以下规则配对对象:

如果i != j，O_i可以与O_j配对，
else if i == j, O_i 不能与 O_j 配对。

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

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

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

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

那么至少存在一种有效的配对方式:

2 个 O₁ 和 2 个 O₂ 配对，4 个 O₁ 和 4 个 O₃ s 配对，4 个 O₁ 和 4 个 O₄ 配对。

一个有效的配对顺序是:

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

Answer 1

检查 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] .

第二个循环很简单。由于正好一半的对象属于 m 类型, 每个类型的对象 m可以与不同类型的对象配对。