0

もちろん、電話インタビュー中にそれを尋ねられました。他の質問は問題ありませんが、それはまだ最善の答えがわかりません.

最初は基数ソートのにおいがすると思っていましたが、隣接するスワップしか使用できないため、もちろん使用できません。

だから私はそれがバブルソートタイプのアルゴリズムだと思います.

私のアルゴは次のようなものになると思います（もちろん、今ではインタビュー中よりも優れたアイデアがあります！）

int index = 0;
while(swapsLeft>0 && index < arrays.length)
{
  int smallestIndex = index;
  for(int i=index; i < index + swapsLeft)
  {
    // of course < is not correct, we need to compare as string or "by radix" or something
    if(array[i]) < array[smallestIndex]
       smallestIndex = i; 
  }
  // if found a smaller item within swap range then swap it to the front
  for(int i = smallestIndex; i > index; i--)
  {
    temp = array[smallestIndex]; 
    array[smallestIndex] = array[index];
    array[index] = temp
    swapsLeft--;
  }
  // continue for next item in array
  index ++; // edit:could probably optimize to index = index + 1 + (smallestIndex - index) ?
}

それは正しいと思いますか？

より良い解決策として、これを行うための効率的/適切な方法に興味があります。

4

1 に答える 1

0

私は実際に、ソフトウェア エンジニアリングの学士号を取得するために、Java でアルゴリズム クラスのこの正確なコードを作成する作業を行っています。そのため、問題とそれを解決する手順を説明することで、これを解決するのに役立ちます. これを複数回行うには、少なくとも 2 つの方法が必要になります。

最初に最初の値を取得します。これを簡単にするために、小さくシンプルに保ちます。

1 2 3 4

並べ替えには配列を使用する必要があります。語彙論的に次の数字を見つけるには、右端から始めて左に移動し、最初の減少を見つけたときに停止します。その小さい値を右側の次に大きい値に置き換える必要があります。この例では、3 を 4 に置き換えます。次の数字は次のとおりです。

1 2 4 3

それはとても簡単でしたよね？心配する必要はありません。次を使用して次の番号を取得してみましょう。

1 4 3 2

では、右端から始めて、最初の小さい数まで左に移動します。2 は 3 より小さい 4 は 1 より大きい1、3 は 1 よりも大きく、2 は 1 よりも大きいです。2 が最後の数字であることは、1 を 2 に置き換える必要があることを意味します。必要なものの後方。したがって、順序を反転する必要があり、次のようになります。

2 1 3 4

したがって、その並べ替えを行うメソッドと、正しい数のパラメーターを実行するまでループ内でそのメソッドを呼び出す別のメソッドが必要です。

于 2014-08-01T14:44:41.163 に答える