アレイからの偶数の削除と正面への奇数の移動

Question

まず第一に、宿題ではありません。私は最後のインタビューでこの質問を受け取り、それを完了できませんでした。

質問には次のようなものがありました。「長さnのint配列kを与え、すべての偶数を削除して、奇数を前に移動する」。彼らは削除と言ったのでちょっと変わったと言われましたが、例では配列の前にすべての奇数を置くだけでいいです（0のインデックスから始まります）。偶数も配列に残ることができます）すべての奇数の後に。 例：

{1, 4, 6, 8, 7, 2} -> {1, 7, whatever} 
{2, 4, 6, 9, 5} -> {9, 5, whatever} 

私は可能な限り効率的にしたいと思います。私は追加のライブラリや一時的な配列を使用することができませんでした。

は、これまでのところ、これを得たが、立ち往生しています：

private static void removeEven(int[] k, int n) { 
for (int i = 0; i < n; i++) { 
    if (k[i] % 2 == 0) { 
    k[i] = // don't know 
    } 
} 

Answer 1

戻り値の配列位置を記憶するためにループ内にカウンタが必要な場合があります。 私はこのコードを使用して、残りの配列位置をすべて0にします。

private static void removeEven(int[] k, int n) { 
    int counter = 0; 
    for (int i = 0; i < n; i++) 
     if (k[i] % 2 == 1) 
      k[counter++] = k[i]; 
    for (int i=counter; i<n; i++) 
     k[i] = 0; 
} 

この回答をお寄せください。

Answer 2

どのように最初のオッズを持つ配列を返します。次の擬似コードのようなもの、最後に追いついて、奇数と偶数の元の順序を保持しますについてサブセット。

if array.length < 2 
    return array 
else 
    p=0 
    while array[p].odd and p < array.length 
    p++ 
    q = p+1 
    if q < array.length 
    repeat 
     if array[q].odd 
     swap(array,p,q) p++ q++ 
     else 
     q++ 
    until q >= array.length 

Answer 3

私は私が何を意味するか、方法を逆の代わりにしても、私は彼らと彼らは、アレイに残っているものの世話、ので、私のいないものである前に奇妙なものを移動する削除するでしょうアプローチは次のようになります

private static int moveOddToFront(int[] k) { 
    int frontIndex = 0; 
    for (int i = 0; i < k.length; i++) { 
     boolean isOdd = k[i] % 2 != 0; 
     if (isOdd) { 
      k[frontIndex] = k[i]; 
      frontIndex++; 
     } 
    } 

    int newSize = frontIndex; 
    return newSize; 
} 

Answer 4

一時的な変数は、移動する値を置く場所で使用することができます。別の変数を使用して移動する場所を設定します。

コード：

for (int i = 0, j = 0; i < n; i++) { 
     if (k[i] % 2 != 0) { 
      int tempInt = k[j]; 
      k[j] = k[i]; 
      k[i] = tempInt; 
      j++; 
     } 
    } 

Answer 5

は、私はちょうど、アレイ内の場所を指し示す2つの変数を維持するであろうと思います。 1つは次の偶数（最初から始まる）を指し、1つは次の奇数（最後から始まる）を指します。次の偶数は次の奇数より低いインデックスを持ちますが、スワップします。ここで作業し、コードをテストされます。

public static void main(String[] args) { 
    int[] test = {2, 4, 6, 9, 5}; 
    int currentEven = -1; 
    int currentOdd = test.length; 
    while (currentEven < currentOdd) { 
     currentEven = nextEvenIndex(currentEven + 1, test); 
     currentOdd = nextLastOddIndex(currentOdd - 1, test); 

     if (currentEven < currentOdd) { 
      swap(currentOdd, currentEven, test); 
     } 
    } 

    for (int i = 0; i < test.length; i++) { 
     System.out.print(test[i]); 
    } 
} 

private static int nextEvenIndex(int start, int[] array) { 
    while (start < array.length) { 
     if (array[start] % 2 == 0) { 
      return start; 
     } 
     start++; 
    } 
    return -1; 
} 

private static int nextLastOddIndex(int start, int[] array) { 
    while (start >= 0) { 
     if (array[start] % 2 == 1) { 
      return start; 
     } 
     start--; 
    } 
    return -1; 
} 

private static void swap(int index1, int index2, int[] array) { 
    int swap = array[index1]; 
    array[index1] = array[index2]; 
    array[index2] = swap; 
} 

これは、私はあなたがここに来ることができると思う最高のパフォーマンスであるO（n）と、です。

これは、数値が決して2回スワップされないため、他の多くの回答よりも優れています。つまり、これらの他のソリューションの大部分はアレイ全体を反復する（時には不必要なスワップを行う）一方で、これは半分しか反復しません。ここで

Answer 6

は、ソリューションです：

private static int[] removeEven(int[] k, int n) { 
      for (int i = 0; i < n; i++) { 
       if (k[i] % 2 == 0) { 
        for(int j=i+1; j<n; j++){ 
         if(k[j] % 2 != 0){ 
          k[i] = k[i] + k[j]; 
          k[j] = k[i] - k[j]; 
          k[i] = k[i] - k[j]; 
          break;//if we get a odd number then we swap it with the even one and so we need not need to proceed the inner loop as the k[i] is already swaped with an oddd number 
         } 
        } 
       } 
      } 
      return k; 
     }