需要優化算法 - 陣列

我們有一個整數大小爲N的數組A.給定另一個包含索引的數組B，其中size of B <= N和0<=B[i]<=N-1。需要優化算法 - 陣列

現在我們必須從位置B[i]的陣列A中刪除所有元素。

因此，與刪除我們的意思，我們也換擋元件陣列A.

有人能幫助我達成對於這個問題O(n)解決方案？可能還有O（1）空間。

我想到的第一個解決方案是遍歷數組B並按順序刪除A中的元素（包括移位），但它是O(n^2)。

來源

2011-06-09 learner

B的元素是否按某種順序排序？如果你也在移動A，B中元素的順序很重要。 – SubmittedDenied 2011-06-09 15:42:49

你有這些數字的限制嗎？我的意思是，你可以使用一些特殊的值來標記某個元素爲「已被刪除」嗎？如果是這樣，這將是一個容易的。 – 2011-06-09 15:42:52

@Kiril，不允許標記已被訪問/刪除的元素:( – learner 2011-06-09 15:45:58

與iliaden的解決方案類似，除非您可以刪除已刪除的元素。

int[] a = 
int[] b = 
int nullValue = 
for(int i: b) a[i] = nullValue; 
int j=0; 
for(int i=0; i < a.length; i++) { 
    if(a[i] != nullValue) 
     a[j++] = a[i]; 
} 
// to clear the rest of the array, if required. 
for(;j<a.length;j++) 
    a[j] = nullValue;

注意：a不會更短，但它避免了創建更多的空間。 'j'將具有有效條目的數量a

來源

2011-06-09 15:55:37

偉大的O（n）時間和O（1）空間。完善。非常感謝:) – learner 2011-06-09 16:06:35

我認爲這是可以得到的一樣好，改變數組的大小一般是'O（n）'內存（創建新數組，複製所有內容）。這可能是值得去查閱其餘元素'N-j'元素並在其中寫入空值。 – SubmittedDenied 2011-06-09 16:07:40

該解決方案取決於具有某種空值的A的內容。這通常不是這種情況。如果沒有空值，你必須保持關於哪些元素被分開刪除的信息，以某種類型的位向量。上面的第二個循環只是一個效率較低的版本'std :: remove_if'。 – 2011-06-10 08:01:11

在O（n）的空間，可以這樣做：

橫移數組A中刪除B處每元素[I]（無變速，O（n））的
創建新陣列C，複製從所有非空元素甲成C順序（也爲O（n））
返回陣列C或將它複製回到清除陣列A（O（N））。因此你能做到這一點在O（n）的蒂姆和O（n）的空間

來源

2011-06-09 15:41:13 iliaden

感謝您的回覆。這將工作，但我正在尋找O（1）的空間和O（n）的時間。 – learner 2011-06-09 15:48:37

沒有標記，O(n)時間，也O(n)空間，在僞代碼：

// create a boolean array indicating which elements are to be deleted 
D = new boolean[N] 
fill(D, false) 
for (b in B) { 
    D[b] = true 
} 

// compact `A in place 
src = 0 
dest = 0 
while (src < N) { 
    if (!D[src]) { 
    A[dest++] = A[src] 
    } 
    src++ 
} 

new_N = dest

來源

2011-06-09 15:53:31 NPE

如果你可以假設b的排序，你遍歷你可以轉移（您可以排序在O b（N *的log（n））如果不）

int[] b; 
int[] a; 
int first=0,bInd=0; 
for(int i = 0;i<a.length;i++){ 
    if(bInd>=b.length || b[bInd]!=i){ 
     a[first]=a[i]; 
     first++; 
    }else{ 
     bInd++; 
    } 
}

來源

2011-06-09 15:54:38

當你移動A時，你不能排序B，因爲A中項目的位置發生了變化.B可能是'[0，0]'，這表示你需要刪除A中的前兩個元素。 – SubmittedDenied 2011-06-09 16:03:05

@submitted我是假設這裏B中的元素是數組A **中的精確索引**在任何刪除之前**因此'b = [0,0]'將無效或意味着只有第一個應該被刪除 – 2011-06-09 16:10:42

@submittedDenied，Sorting wont effect真正的解決方案。 B中的索引是初始數組。移位對陣列B不會產生任何影響。 – learner 2011-06-09 16:13:25

兩個顯而易見的解決方案：排序B以相反的順序開始之前，所以你總是刪除最高的索引（所以永遠不要移動已刪除的元素），或迭代通過B創建一個要刪除元素的位圖（然後然後做相反的順序）。第一個需要額外的步驟 O(lg n)，第二個額外的空間。但我不是肯定有更好的選擇。

來源

2011-06-09 15:55:02

B的順序很重要，你不能對它排序。另外，即使按升序或降序排列，您也需要將位於已刪除元素右側的元素（即具有較高索引的元素）移到左側。 – SubmittedDenied 2011-06-09 15:59:22

@SubmittedDenied每當你從一個'std :: vector'中移除一個元素（除非它是最後一個元素），你必須改變其他元素。但是像'std :: remove_if'這樣的函數實際上並不會刪除元素;一旦他們將要保留的元素轉移到開始位置，就會在最後刪除一組元素。從後面開始的原因是您不會使未處理的索引失效。如果你不能對'B'進行排序，那麼唯一的解決方法就是使用位向量;之後，您可以使用'std :: remove_if'和'erase'，或'copy_if'。 – 2011-06-10 07:58:28

需要優化算法 - 陣列

回答

相關問題