0

我在 .txt 文件中有一大组 (S) 长无符号整数。如何找到具有以下属性的 S 的最大子集 (Pmax)：

P{X1,X2,X3,...,Xn) | X1>=(Xn/4)

更多细节：

  1. 当我说最大子集时，我的意思是元素数量最多的子集（n->max）。
  2. 由于内存有限，我无法将 .txt 加载到数组中。
  3. 我的系统内存是200MB
  4. txt 文件有 10^6 个整数。每个整数可以是长无符号 32 位。
  5. 我需要找到具有以下条件的 S 的最大子集：

X1 < X2 < X3 < ... < Xn-1 < Xn 如 X1 >= (XN/4)

例如，如果 txt 文件具有以下内容：15,14,13,4,2,2,3,10,1,2,2 那么这些是可能的子集：

P1(4,10,13,14,15)

P2(3,4,10)

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

所以 Pmax(1,2,2,2,2,3,4) 因为它有更多的元素。

事实上，我不想确切地找到哪个是 Pmax。我只想找到子集 Pmax 的元素数。所以这里是7。

该算法应该非常快。

我不找人来做我的工作。我只需要一个相应的问题，这样我就可以寻找有效的解决方案。提前致谢！！！

4

2 回答 2

1

假设您的条件意味着“子集中的所有元素都大于 X1 除以 4”，您需要 2 个简单的嵌套循环和一些辅助变量。

在伪代码中，这样的东西应该可以工作：

var idx = 0, largest = 0, currentIdx = 0;

while(var current = getIntegerFromFileById(currentIdx))
{
  var size = 1;
  while(getIntegerFromFileById(currentIdx + size++) > current / 4);
  if(size > largest) {
    idx = currentIdx;
    largest = size;
  }
  currentIdx++;
}
print "Longest subset is at index {idx}.";
print "It contains {largest} consecutive elements.";

这也是事实上的最优实现。最明显的优化是在扫描期间将整数逐步加载到内存缓冲区中，以防止双重 I/O 操作。

万一我误解了这个条件，这应该仍然很容易适应大多数其他条件，周围的算法保持不变，你只需在内部修改条件。

于 2013-04-12T21:55:42.667 回答
0

最简单的解决方案是：

  1. 首先对列表进行排序（复杂度 O(nlogn)
  2. 使用移动窗口，找到最大的可接受窗口。（复杂度 O(n)）

复杂度：O(nlogn)。

关于第 2 步的更多详细信息：

让 low 跟踪最低元素，让 high 跟踪最高元素。

初始化：将第一个元素设置为低。对 4*x[low] 进行二分搜索，这就是你的高位。设置 maxWindow=high-low+1。

在每一步：将 high 增加 1，并增加 low 使得 x[low]>=x[high]。计算元素数 = high-low+1，并相应更新 maxWindow。

于 2013-04-12T23:01:08.000 回答