找到一大组整数的最大子集

我有一个巨大的集合（S）长的无符号整数.txt文件。我怎样才能找到最大的子集S的（P最高）具有以下属性：找到一大组整数的最大子集

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

更多细节：

当我说最大的子集我指的是元素的最大数（n子集 - >最大）。
由于内存有限，无法将.txt加载到数组中。
我的系统内存200MB是
txt文件有10^6的整数。每个整数可以是长整型无符号32位。
我需要找到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）

所以P最高（1,2,2,2,2,3,4 ），因为它有更多的元素。

其实我并不想准确地找到这是P最高。我只想找到子集Pmax的元素数量。所以这里是7.

该算法应该非常快。

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

来源

2013-04-12 chris k.

你_memory_是200MB？或者你的文件？另外，“P”是什么？而'''你的意思是“这样的”？ – Shahbaz

另外，在本网站中，我们试图帮助您，而不是您的工作。你至少需要表现出一些努力。你已经尝试了什么？通过在谷歌上搜索发现了什么，为什么你没有找到足够用于你的目的？ – Shahbaz

我可能会误解你写下这个条件的方式，但是你是不是要写出子集中的所有数字都大于X1？您现在编写它的方式最大的子集几乎是按照定义的整个文件。 –

的最简单的解决方案是：

排序列表第一（复杂度O（nlogn）
随着移动窗口，找到最大的可接受窗口。（复杂度O（n））

复杂度：O（nlogn）。

更多细节第二步：

让最低元素和高最高的元素的低跟踪。

初始化：设置低的第一要素。做一个二进制搜索4 * x [低]，这是你的高位置。设置maxWindow = high-low + 1。

在每一个步骤：递增1高，并增加低，使得x [低]> = X [高]。计算元素数量= high-low + 1，并相应地更新maxWindow。

来源

2013-04-12 23:01:08 ElKamina

非常感谢您的回答！但是我怎样才能排序的txt文件中的数据，因为我不能加载到列表或数组？在txt文件中排序它不会很慢吗？ –

@chrisk。有许多常量内存排序算法（例如MergeSort）。你可以使用它或者在linux中使用命令行排序功能。无论如何，这可以在O（nlogn）时间完成。这是一个真正的问题还是面试/测试问题？ – ElKamina

谢谢。这不是一个真正的问题。这是一个测试问题，所以我不能预设txt文件... –

假设你的条件是指“在子集中的所有元素比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-12 21:55:42

复杂度为O（n^2）。你可以做得更好。见下文。 – ElKamina

我在对条件进行了几次澄清之前发布了我的解决方案。对于我所假设的TS来说，这意味着这是最佳的解决方案，因为它不清楚元素不必是有序的（因为这样不包括从选项中排除，也不可能在一般的约束条件下）。 –

对不起，我没有明确问题。我非常感谢你的帮助。谢谢 –

找到一大组整数的最大子集

回答

相关问题