时间戳

首页 > 解决方案 > 在 O(lg n) 中查找 Python 列表的唯一数字对中的单个数字

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

问题描述

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

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

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

  1. [2,2,2,2,3,3,4]（违反条件1：因为有两对2，而任意数最多只能有1对）
  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) 时间了？

编辑：曼努埃尔似乎有最好的解决方案，如果允许的话，我将有时间自己实施解决方案以供理解，然后接受曼努埃尔的回答。

标签： pythonlistdivide-and-conquer

解决方案

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 在2*x + 1（数组长度）中的奇偶性影响是搜索输入的左侧还是右侧：如果 x 为奇数则搜索右侧，如果 x 为偶数则搜索左侧，如果 middle_number == left_number（反之亦然）。

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

def find_single_number(array: list, start_index: int, end_index: int):
    # base case: array length == 1
    if start_index == end_index:
        return start_index
    
    middle_index = (start_index + end_index) // 2
        
    # base case: found target
    if array[middle_index] != array[middle_index - 1] and array[middle_index] != array[middle_index + 1]:
        return middle_index
        
    # make use of parity of array length to search left or right side
    # end_index == array length - 1
    x = (end_index - start_index) // 2

    # ensure array length is odd
    include_middle = (middle_index % 2 == 0)
        
    if array[middle_index] == array[middle_index - 1]:  # middle == number on its left
        if x % 2 == 0:  # x is even
            # search left side
            return find_single_number(
                array,
                start_index,
                middle_index if include_middle else middle_index - 1
            )

        else:  # x is odd
            # search right side side
            return find_single_number(
                array,
                middle_index if include_middle else middle_index + 1,
                end_index,
            )

    else:  # middle == number on its right
        if x % 2 == 0:  # x is even
            # search right side side
            return find_single_number(
                array,
                middle_index if include_middle else middle_index + 1,
                end_index,
            )

        else:  # x is odd
            # search left side
            return find_single_number(
                array,
                start_index,
                middle_index if include_middle else middle_index - 1
            )


# test out the code
if __name__ == '__main__':
    array = [2,2,1,1,3,3,4,5,5,6,6]  # target: 4 (index: 6)
    print(find_single_number(array, 0, len(array) - 1))

    array = [1,1,2]  # target: 2 (index: 2)
    print(find_single_number(array, 0, len(array) - 1))

    array = [1,1,3,2,2]  # target: 3 (index: 2)
    print(find_single_number(array, 0, len(array) - 1))

    array = [1,1,4,2,2,3,3]  # target: 4 (index: 2)
    print(find_single_number(array, 0, len(array) - 1))

    array = [5,1,1,2,2,3,3,4,4]  # target: 5 (index:0)
    print(find_single_number(array, 0, len(array) - 1))

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

证明它的时间复杂度为 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 0 ) = 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 k-k ) + k = T(2 0 ) + k = k + 1

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

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

1 是一个常数，所以可以去掉；日志操作的基础也是如此。

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

推荐阅读