在 O(lg n) 中查找 Python 列表的唯一数字对中的单个数字

Question

我有一个关于编程算法中的分而治之的问题。假设你在 Python 中得到一个随机整数列表，它包括：

1. 唯一连续的整数对
2. 列表中某处的单个整数

并且条件是排他的，这意味着虽然[2,2,1,1,3,3,4,5,5,6,6]有效，但这些不是：

1. [2,2,2,2,3,3,4] （违反条件1：因为有两对2，而任何数字最多只能有一对）
2. [1,4,4,5,5,6,6,1] （违反条件 1：因为有一对 1 但它们不连续）。
3. [1,4,4,5,5,6,6,3] （违反条件2：有2个单号，1和3）

现在的问题是你能在 O(lgn) 算法中找到“单个”数字索引吗？

我原来的刺拳是这样的：

def single_num(array, arr_max_len):

  i = 0

  while (i < arr_max_len):
    if (arr_max_len - i == 1):
      return i
    elif (array[i] == array[i + 1]):
      i = i + 2
    else:
      return i # don't have to worry about odd index because it will never happen
  
  return None 

然而，该算法似乎以 O(n/2) 的时间运行，这似乎是它所能做的最好的。

即使我使用分而治之，我也不认为它会比 O(n/2) 时间更好，除非有一些方法超出了我目前的理解范围。

任何人都有更好的主意，或者我可以说，这已经是 O(log n) 时间了吗？

编辑：似乎 Manuel 有最好的解决方案，如果允许的话，我将有一些时间自己实施解决方案以进行理解，然后接受 Manuel 的回答。

Answer 1

解决方案

只需对偶数索引进行二分搜索即可找到第一个值与下一个值不同的值。

from bisect import bisect

def single_num(a):
    class E:
        def __getitem__(_, i):
            return a[2*i] != a[2*i+1]
    return 2 * bisect(E(), False, 0, len(a)//2)

解释

E()我正在搜索的虚拟“列表”的可视化：

       0  1   2  3   4  5   6  7   8  9   10 (indices)
  a = [2, 2,  1, 1,  3, 3,  4, 5,  5, 6,  6]
E() = [False, False, False, True,  True]
       0      1      2      3      4     (indices)

一开始，这些对匹配（因此!=结果为False-values）。从单个数字开始，对不匹配（因此!=返回True）。因为False < True，这是一个可以bisect愉快搜索的排序列表。

替代实现

没有bisect，如果您还没有厌倦编写二进制搜索：

def single_num(a):
    i, j = 0, len(a) // 2
    while i < j:
        m = (i + j) // 2
        if a[2*m] == a[2*m+1]:
            i = m + 1
        else:
            j = m
    return 2*i

叹...

我希望bisect支持给它一个可调用的，这样我就可以做return 2 * bisect(lambda i: a[2*i] != a[2*i+1], False, 0, len(a)//2). Ruby 可以，这可能是我有时使用 Ruby 而不是 Python 解决编码问题的最常见原因。

测试

顺便说一句，我对最多 1000 对的所有可能情况进行了测试：

from random import random

for pairs in range(1001):
    a = [x for _ in range(pairs) for x in [random()] * 2]
    single = random()
    assert len(set(a)) == pairs and single not in a
    for i in range(0, 2*pairs+1, 2):
        a.insert(i, single)
        assert single_num(a) == i
        a.pop(i)

Answer 2

lg n 算法是将输入分成更小的部分，并丢弃一些更小的部分，这样您就可以使用更小的输入。由于这是一个搜索问题，因此 lg n 时间复杂度的可能解决方案是二分搜索，其中每次将输入分成两半。

我的方法是从几个简单的案例开始，找出我可以利用的任何模式。

在以下示例中，最大的整数是目标数。

# input size: 3  
[1,1,2]
[2,1,1]

# input size: 5  
[1,1,2,2,3]
[1,1,3,2,2]
[3,1,1,2,2]

# input size: 7  
[1,1,2,2,3,3,4]
[1,1,2,2,4,3,3]
[1,1,4,2,2,3,3]
[4,1,1,2,2,3,3]

# input size: 9  
[1,1,2,2,3,3,4,4,5]
[1,1,2,2,3,3,5,4,4]
[1,1,2,2,5,3,3,4,4]
[1,1,5,2,2,3,3,4,4]
[5,1,1,2,2,3,3,4,4]

您可能注意到输入大小始终是奇数，即2*x + 1.

由于这是一个二分搜索，您可以检查中间数字是否是您的目标数字。如果中间的数字是单个数字 ( if middle_number != left_number and middle_number != right_number)，那么您已经找到了。否则，您必须搜索输入的左侧或右侧。

请注意，在上面的示例测试用例中，中间数字不是目标数字，中间数字与其对之间存在模式。

对于输入大小 3 (2*1 + 1), if middle_number == left_number，目标数在右边，反之亦然。

对于输入大小 5 (2*2 + 1), if middle_number == left_number，目标数在左边，反之亦然。

对于输入大小 7 (2*3 + 1), if middle_number == left_number，目标数在右边，反之亦然。

对于输入大小 9 (2*4 + 1), if middle_number == left_number，目标数在左边，反之亦然。

这意味着 x in 2*x + 1（数组长度）的奇偶性会影响是搜索输入的左侧还是右侧：如果 x 是奇数，则搜索右侧，如果 x 是偶数，则搜索左侧，如果 middle_number == left_number（反之亦然） ）。

基于所有这些信息，您可以提出递归解决方案。请注意，您必须确保每次递归调用中的输入大小都是奇数。（编辑：确保输入大小是奇数会使代码更加混乱。您可能想提出一个解决方案，其中输入大小的奇偶校验无关紧要。）

# input size: 3  
[1,1,2]
[2,1,1]

# input size: 5  
[1,1,2,2,3]
[1,1,3,2,2]
[3,1,1,2,2]

# input size: 7  
[1,1,2,2,3,3,4]
[1,1,2,2,4,3,3]
[1,1,4,2,2,3,3]
[4,1,1,2,2,3,3]

# input size: 9  
[1,1,2,2,3,3,4,4,5]
[1,1,2,2,3,3,5,4,4]
[1,1,2,2,5,3,3,4,4]
[1,1,5,2,2,3,3,4,4]
[5,1,1,2,2,3,3,4,4]

我的解决方案可能不是最有效或最优雅的，但我希望我的解释能帮助您理解解决此类算法问题的方法。

证明它的时间复杂度为 O(lg n)：

让我们假设最重要的操作是将中间数字与左右数字 ( if array[middle_index] != array[middle_index - 1] and array[middle_index] != array[middle_index + 1]) 进行比较，并且它的时间成本为 1 个单位。让我们将此比较称为主要比较。

令 T 为算法的时间成本。
令 n 为数组的长度。

由于此解决方案涉及递归，因此存在基本情况和递归情况。

对于基本情况 (n = 1)，它只是主要比较，因此：
T(1) = 1。

对于递归情况，每次将输入分成两半（左半部分或右半部分）；同时，有一个主要的比较。所以：
T(n) = T(n/2) + 1

现在，我知道输入大小必须总是奇数，但为了简单起见，让我们假设 n = 2 ^k；时间复杂度仍然相同。

我们可以将 T(n) = T(n/2) + 1 改写为：
T(2 ^k ) = T(2 ^k-1 ) + 1

此外，T(1) = 1 是： T(2 ⁰ ) = 1

当我们展开 T(2 ^k ) = T(2 ^k-1 ) + 1 时，我们得到：

T(2 ^k )
= T(2 ^k-1 ) + 1
= [T(2 ^k-2 ) + 1] + 1 = T(2 ^k-2 ) + 2
= [T(2 ^k-3 ) + 1 ] + 2 = T(2 ^k-3 ) + 3
= [T(2 ^k-4 ) + 1] + 3 = T(2 ^k-4 ) + 4
= ...(重复直到 k)
= T(2 ^kk ) + k = T(2 ⁰ ) + k = k + 1

由于 n = 2 ^k，这意味着 k = log ₂ n。

将 n 代入，我们得到： T(n) = log ₂ n + 1

1 是一个常数，所以它可以被删除；日志操作的基础也是如此。

因此，算法时间复杂度的上限为：
T(n) = lg n