找到一大組整數的最大子集

我有一個巨大的集合（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來說，這意味着這是最佳的解決方案，因爲它不清楚元素不必是有序的（因爲這樣不包括從選項中排除，也不可能在一般的約束條件下）。 –

對不起，我沒有明確問題。我非常感謝你的幫助。謝謝 –

找到一大組整數的最大子集

回答

相關問題