訪問Java中的每個通用列表幾個元素只有一次

我有一個Java列表，我想利用每一個元素訪問一次。例如，如果我有一個數組我會做這樣的：訪問Java中的每個通用列表幾個元素只有一次

O[] x = ...; 
for(int i = 0; i<x.length; i++){ 
    for(int j=i+1; j<x.length;j++){ 
      someOperation(x[i],x[j]); 
    } 
}

的問題是，我有一個List（我們假設到不知道該列表是一個ArrayList或一個LinkedList）。爲了具有相同的複雜性，上市前的情況下，我會在僞代碼，像寫：

ListIterator<O> it1 = list.listIterator(); 
while(it1.hasNext()){ 
     O x = it1.next(); 
     it2 = it1.clone(); //it2 have the same "status" of it1, but it is a different object in memory 
     while(it2.hasNext()){ 
      y= it.next(); 
      someOperation(x,y); 
     } 
}

據我所知，我們沒有像it1.clone任何東西（）。做類似的東西，唯一的辦法是或多或少：

int i = it1.nextIndex(); 
it2 = list.listIterator(i);

，但據我所知，

list.listIterator(i);

可以有一個爲O（n）的複雜性 - 在的情況下，一個LinkedList，這在其他語言中是絕對可以避免的。另一方面，使用隨機訪問（如list.get（i））來實現相同的算法會更糟糕。假設列表是一個LinkedList，編寫代碼的正確方法是什麼？

來源

2016-02-05 Samuele

您可以在剛開始時將'LinkedList'複製到'ArrayList'，即O（n）。然後對它進行配對操作。這是一個額外的O（n），它不增加複雜性和一些額外的空間。 – MGoksu

如果你去了另一個方向怎麼辦？隨時創建新列表並累積元素。 – matt

@BoristheSpider你是對的，我錯過了那部分問題。 – Thomas

你就不能換i和j？

List<E> x = ...; 
int j = 0; 
for (E ej : x) { 
    int iMax = j++; 
    int i = 0; 
    for (E ei : x) { 
     if (i++ >= iMax) 
      break; 
     someOperation(ei, ej); 
    } 
}

來源

2016-02-05 14:58:40

這是我認爲迄今爲止最有效的解決方案，甚至更簡單的一個：不涉及迭代器，並且不需要額外的內存:)謝謝 – Samuele

@Samuele歡迎您。順便說一句，迭代器隱含在「for-each」循環中。 –

我認爲最好的解決方案是使用list.listIterator(i)。

在LinkedList的情況下，這是O（n），但算法的複雜性仍然是O（n^2）。就Big-Oh而言，它不會改變任何事情！

乾杯

來源

2016-02-05 14:31:05 virsox

你說得對，就Big-O而言沒有什麼變化，但是你的代碼 - 如果是鏈表 - 會花費大約兩倍的時間，在我看來，這是不好的。 – Samuele

如果你可以修改列表：

Iterator<Items> things = list.iterator(); 

while(things.hasNext()){ 
    Item item = things.next(); 
    things.remove(); 
    Iterator<Item> others = list.iterator(); 
    while(others.hasNext()){ 
     //... do stuff; 
    } 
}

如果順序並不重要，你可以建立一個新的列表。

List<Item> others = new ArrayList<>(list.size()); 
for(Item item: list){ 
    for(Item other: others){ 
     // do stuff 
    } 
    others.add(item); 
}

來源

2016-02-05 14:35:20 matt

我認爲這是解決問題的最好方法，即使在這之前我必須複製列表。我創建了爲什麼我們沒有像iterator.clone（）這樣的東西。在我看來會容易得多。 – Samuele

@BoristheSpider我不同意你的看法，事實上，在刪除操作之後，matt會創建第二個迭代器 – Samuele

@BoristheSpider我認爲每個對象都使用a，但我不確定。這兩個迭代器[作品]（http://ideone.com/k5WEq2）。儘管修改列表可能會增加比列表迭代器解決方案更多的開銷。 – matt

訪問Java中的每個通用列表幾個元素只有一次

回答

相關問題