小编Ros*_*g X的帖子

我有一个关于编程算法中的分而治之的问题。假设你在 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 …

我正在Haskell中处理一个函数,它接收Ints和Int的列表.

sublistSum :: [Ints] -> Int -> [[Ints]]

它返回的是一个子列表,其中包含原始列表中与Int相加的数字列表.

例如:

sublistSums [1, 5, -2, 4, 3, 2] 2
[[1,-2,3],[-2,4],[2]]

我的工作:

sublistSums [] num = []
sublistSums (x:xs) num  
    | findSum x xs num == num = findSum x xs num 0 : sublistSums (x:xs) num
    | otherwise = sublistSums xs num

findSum x [] num count = []
findSum x (y:ys) num count
    | ...

所以findSum我做的辅助函数应该返回这样的数字列表(加起来这个数字).

到目前为止我有点困惑.我如何标记它以便findSum不会反复给我相同的数字列表？