誰かがこの方法の仕組みを説明できますか？

Question

この方法では、人口が最も少ない都市を削除しようとしています。

方法：

public void delCity(long population) { 
    if (population== 0) { 
     System.out.println("There is no city!"); 
     return; 
    } 

    for (int i = 0; i < index; i++) { 
     if (cities[i].getPopulation() < population) { 
      for (int j = i; j < index - 1; j++) { 
       cities[j] = cities[j + 1]; 
      } 
      cities[--index] = null; 
      i--; 
     } 
    } 
} 

ので、私は理解していない部分は、forループ第二のボディは、例えば、どのようにcities[j] = cities[j + 1];作品やcities[--index] = null; i--;を何でしょうか？私は本当にあなたの反応に感謝します。

Answer 1

このループは、[iの位置（削除する都市）から配列のすべての値をシフトしています。（配列が静的なので、そうでない場合は要素間にnullがあります）

for (int j = i; j < index - 1; j++) { 
    cities[j] = cities[j + 1]; 
} 

次に、最後の要素をNULLに設定し、インデックスを減らしています。ここ

cities[--index] = null; 

変速のexplainationは：

コメントに述べたように。あなたの複雑さはO（N²）です。しかし、単にリストを使ってデータ構造を変更するだけで、O（N）に改善することができます。

Answer 2

cities[j] = cities[j + 1]; 

上記の文は、インデックスj + 1で街にインデックスjで都市を設定します。

cities[--index] = null; 

この文は単にnullに都市の最後のインデックスを設定します。

このように、要素の除去はありません。削除される要素は次の要素で上書きされます。そしてループは、削除される要素に続くすべての要素に対してこれを行います。最後に、最後の要素はnullに設定されています。

説明を省略すると、コードは非常に非効率的です。

Answer 3

indexは、配列citiesのサイズです。だから、あなたはcities[i].getPopulation() < populationがtrueある特定の位置に来たとき、あなたは位置index - 2からiに配列index - 1の最後に位置i + 1からすべての都市を移動し、あなたがそれを行う：だから

for (int j = i; j < index - 1; j++) { 
       cities[j] = cities[j + 1]; 
      } 

、との都市配列iの小さな集団であるjは、citiescities[j + 1]で上書きして削除され、citiescities[j + 1]は、配列の最後までcitiescities[j + 2]などで上書きされます。だから、位置citiescities[index - 2]にcitiescities[index - 1]と同じになりますので、あなたはindexは、最初の（--がindexから残されるThatsなぜ）デクリメントされ、cities[oldIndex - 1]はnullなりますcities[--index] = null;を置くので、私たちは、それを削除する必要があります。これはまたforのループが最初のindexの配列の値の場所まで行くことを助け、arrayの最後の都市まで存在します。

今、あなたのインデックス以来、私はループステップのための次にインクリメントされますが、あなたはその都市をチェックするiをデクリメントしなければならない、私の位置に次の街を移動し、最後になぜiのthats。

これと同じように、これまでのように完全な長い配列を持つことになります。したがって、人口が少ない都市がある場合は、いくつかのヌルが入ります。たぶんより良いアプローチは、サイズindexの新しい配列にコピーすることです。forの末尾にあることに注意してください（注：項目を削除するときにArrayListと同じものがあります）。

Answer 4

私は、このような単純な文脈では、もっと複雑な説明が余分にあるので、コードにコメントしました。

//Scan all the cities, from i = 0 to i = index -1 
for (int i = 0; i < index; i++) 
{ 
    //Check it cities[i] has LESS population than specified 
    if (cities[i].getPopulation() < population) 
    { 
     //We need to remove cities[i] 
     //We shift all the subsequent cities 
     //(cities[i+1], cities[i+2], ... cities[index-1] one position LEFT, 
     //thereby overwriting cities[i] and so deleting it 

     //Shift all the subsequent cities left 
     //We start this for FROM i, so the first iteration is 
     //cities[i] = cities[i + 1]; 
     //The second is 
     //cities[i + 1] = cities[i + 2]; 
     //and so on. We STOP AT index - 2 (note the strict less than) 
     //So that j + 1 is AT MOST index - 1 
     for (int j = i; j < index - 1; j++) 
     { 
       cities[j] = cities[j + 1]; 
     } 

     //Since j was at most index - 2, the cities[index - 1] was not 
     //overwritten with the next one. Naturally as there is no next one 
     //for it. 
     //This last city is now duplicated (the copy is at index - 2) and 
     //Must be overwritten with null. 
     //Also index, which keep track of the number of cities must be 
     //decremented (here the pre-decrement -- is used) 
     cities[--index] = null; 

     //cities[i] was the deleted city. But now it contains cities[i + 1] 
     //Which is a totally different city! 
     //If we continue the for now, we will go to the NEXT city, as i 
     //will be incremented, to keep i the same one more iteration, we 
     //decrement it. This way we process (the new) cities[i] one more time. 
     i--; 
    } 
} 

アルゴリズムを完全に理解するまで、古いペンシルとゴムを使用してください。本当に良い方法はありません。