“分治”算法任务

Question

现在我有N个不同的整数，我需要找到一个区间，在O(NlogN)时间内具有最多数量的数字，这些数字的值在区间的端点之间。我称之为“分治”问题，因为它属于我的期末考试的“分治”类别。我已经思考了两周，并进行了许多实验，但都没有得出正确的答案（与暴力算法相比）。有人能帮帮我吗？

例子：

8,1,3,4,7。答案是1-7。

2,6,5,4,9,8。答案是2-9或2-8。

我认为“区间”这个词并不能表达我的意思。我的意思是找到一个子序列，其中有最多的数字的值在子序列的端点之间。例如1：“1,3,4,7”有两个数字（3,4），例如2：无论是“2,6,5,4,9”还是“2,6,5,4,9,8”，都有三个数字（6,5,4）。

以下是我的代码（O(n^2)）。@Vaughn Cato 我使用这个代码来与你的代码进行比较。

#! /usr/bin/env python
#coding=utf-8
import itertools
def n2(numbers):
  a = [0]*len(numbers)
  ans = -1
  l = 0
  r = 0
  for j in range(1,len(numbers)):
    t = 0
      for i in range(j-1,-1,-1):
        if numbers[i]<numbers[j]:
          x = t - a[i]
          if x>ans:
            ans = x
            l = i
            r = j
          t += 1
        else:
          a[i] += 1
  return (numbers[l],numbers[r],ans)

def countBetween(numbers,left,right):
  cnt = 0
  for i in range(left+1,right):
    if numbers[left]<numbers[i]<numbers[right]:
      cnt += 1
  return cnt

for numbers in itertools.permutations(range(5)):
  ans1=n2(numbers)
  ans2=longestInterval(numbers)
if(ans1[2]!=ans2[2]):
  print ans1,ans2,numbers

- Amos

---

如果你已经坚持了两个星期，那么你可能尝试了一些方法。欢迎分享。 - keyser

有时间区间的限制吗？如果没有，你可以以 O(1) 的时间复杂度输出区间 [MIN_INT, MAX_INT]。 - Henrik

据我理解，您的问题是要找到整数列表的最小值和最大值。使用归并排序（其复杂度为O(N.log(N)）即可解决...但我认为问题并不那么简单，请清楚地阐述您的主题。 - Rerito

抱歉，我已经简化了这个问题，所以我的代码不是很明确。我希望这些例子能够清楚地解释它。 - Amos

@amos，你尝试过什么？假设我有一个数组a[1..N]（wlog，假设N为偶数），我知道a[1...N/2]的解是i,j（i<j），a[N/2+1...N]的解是k,l（k<l），那么对于a来说可以说什么呢？如果a[j]<a[l]怎么办？有多少种情况？ - thang

Answer 1

注意：这实际上并不起作用，但它可能会给你一些想法。

这样考虑：

• 让X成为数字数组。
• 让s成为子序列开始的索引。
• 让e成为子序列结束的索引。

如果选择任意分区索引p，则最长子序列要么跨越此分区，要么向左或向右倒塌。如果最长子序列横跨该分区，则s < p <= e。要找到s，请查找在s和p之间具有最多大于X[s]的数字的索引。要找到'e'，请在p和e之间查找最多的数字，这些数字小于X[e]。

您可以递归地检查左侧和右侧，以查看是否可以找到更长的子序列。

如果您拥有按值排序的X索引列表，则可以在线性时间内查找哪个索引具有最大数量的大于右侧数字或最小数量的左侧数字：

要查找起始索引，请从索引列表的第一个索引开始，假设它是迄今为止最好的。 如果下一个索引大于迄今为止最佳索引，则任何未来的索引都需要比我们当前的最佳索引更向左才能成为新的最佳索引，因此我们从最佳索引减去一（但记住实际上的最佳索引）。 如果下一个索引在最佳索引的左侧，则将其设置为最佳索引。 依次重复此过程，对于每个索引。

您可以执行类似的过程以查找右侧结束的最佳索引。

唯一剩下的技巧是维护我们正在处理的任何范围的排序索引列表。 这可以通过首先对整个数字集进行排序并找到它们的索引，然后在递归的每个级别中，我们可以在线性时间内将排序的索引拆分为两个子列表来完成。

以下是该思路的Python实现：

# Find the index from the given indices that has the most numbers to the
# right of it which are greater in value.  The indices are sorted by
# the value of the numbers at that index. We don't even need to know
# what the numbers are.
def longestLowerSequence(indices):
  best_index=indices[0]
  target_index=best_index
  for i in range(0,len(indices)):
    if indices[i]<target_index:
      best_index=indices[i]
      target_index=best_index
    else:
      target_index-=1
  return best_index

# Find the index from the given indices that has the most numbers to the
# left of it which are less in value.
def longestUpperSequence(indices):
  n=len(indices)
  best_index=indices[n-1]
  target_index=best_index
  for i in range(0,n):
    if indices[n-1-i]>target_index:
      best_index=indices[n-1-i]
      target_index=best_index
    else:
      target_index+=1
  return best_index

# Return the pair of indices which has the most values between it.
def longestRangeFromSortedIndices(numbers,indices,begin,end):
  assert end>begin
  if end-begin<=2:
    return (indices[begin],indices[end-1])
  assert type(indices) is list
  partition=(begin+end)/2
  left_indices=filter(lambda index: index<partition,indices)
  right_indices=filter(lambda index: index>=partition,indices)
  assert len(left_indices)>0
  assert len(right_indices)>0
  left=longestLowerSequence(left_indices)
  right=longestUpperSequence(right_indices)
  left_range=longestRangeFromSortedIndices(numbers,indices,begin,partition)
  right_range=longestRangeFromSortedIndices(numbers,indices,partition,end)
  best_size=countBetween(numbers,left,right)
  best_range=(left,right)
  left_size=countBetween(numbers,left_range[0],left_range[1])
  right_size=countBetween(numbers,right_range[0],right_range[1])
  if left_size>best_size:
    best_size=left_size
    best_range=left_range
  if right_size>best_size:
    best_size=right_size
    best_range=right_range
  return best_range

def sortedIndices(numbers):
  return sorted(range(len(numbers)),key=lambda i: numbers[i])

def longestInterval(numbers):
  indices=sortedIndices(numbers)
  longest_range=longestRangeFromSortedIndices(numbers,indices,0,len(numbers))
  return (numbers[longest_range[0]],numbers[longest_range[1]])

- Vaughn Cato

---

谢谢！但我认为这种方法可能是错误的。我已经将您的代码与暴力代码进行了比较，并发现了这个：（1、3、4、0、2）您的代码给出了（1,2），而答案是（1,4）。 - Amos

@amos：我同意。它假设您可以在分区的每一侧独立找到起始和结束索引，但它们实际上是相互关联的。 - Vaughn Cato

Answer 2

我认为这是最大子数组问题的一个变体。

可以使用分治法解决，具体如下：

1. 将整数数组分成相等的两半

2. 在两个半部分上分别计算结果R1、R2（R1、R2分别是每个半部分最大区间的长度，并存储起始和结束点）

3. 从第一半中获取最小整数MIN，从第二半中获取最大整数MAX，并计算结果R3，即MIN到MAX在原始数组中的距离（Min和Max分别是起始和结束点）

4. 返回R1、R2和R3中最大的作为整个问题的结果

为什么这样做有效：

最大的区间来自以下三种情况之一：1）前半部分 2）后半部分 3）跨越两个半部分。因此，计算这三个中最大的一个可以得到最优结果。

时间复杂度：

解决递归问题：

T(n) = 2T(n/2) + O(n)

给出 T(n) = O(nlogn)。注意：正如递归所示，我们解决两个大小为一半的子问题（2T(n/2)），并在线性时间内找到两个半部分中的最小和最大整数（O(n)）。

- Terry Li

---

谢谢！但我想知道你是否误解了问题。“从前半部分获取最小整数MIN，从后半部分获取最大整数MAX，并计算结果R3为原始数组中MIN到MAX的距离（Min和Max分别是起点和终点）”是不正确的。 - Amos

@amos 我想我忽略了区间内的整数可能不在范围内这一事实。我会将答案保留原样，以防有人从中获得灵感。我会继续努力工作。 - Terry Li