コーディングチャレンジ

概要

それで、最近私はコーディングチャレンジをチェックしていました。この問題は非常に興味深いものでしたので、時間と空間の複雑さの観点から、より良い方法があるかどうか知りたいだけです。

問題: 数値 x が与えられ、x は 0 より大きい正の数になります。同じ数字を異なる順序で並べ替えた最も近い最小の数値を見つけます。存在する場合は最小の数値を返し、そうでない場合は「最も近い最小の数値は存在しません」と出力します。

そこで、以下にいくつかの例を示します

番号: 8563 出力: 8536

番号 7385 出力7358

番号: 3857 出力: 3785

番号: 123 出力: 最も近い最小の数値は存在しません

number = gets.to_i
flag = 1
numbers_array =  number.digits.permutation(Math.log10(number).to_i + 1).sort
numbers_array.each_with_index do |e, index| 
  if e.join.to_i == number
    print numbers_array[index - 1]
    flag = 0
    break
  end
end
if flag == 1
  puts "Nearest Smallest Number not exist"
end

注: 数値が非常に大きい場合、上記の解決策にはさらに時間がかかります。

解決策

この考え方は、配列の次の順列を生成するのと似ています。

順列があるとしましょう

a1, a2, a3 ... an

これの前の順列は何ですか?

観察：最初の順列 (最小のもの) には次の特性があります。

a1 <= a2 <= a3 ... <= an

そして、最後の順列には次の特性があります。

a1 >= a2 >= a3 ... >= an.

この観察から、特定の順列を簡単に行ったり来たりすることができます。

次のような位置 k が見つかった場合、最後の要素から最初の要素まで繰り返してみましょう。

ak , ak + 1, and ak > ak + 1

ak + 1 … an から最大の数を見つけて、ax < ak を満たす ax と呼び、ax を ak に置き換えます。

a1, a2, ... ax, [...]

[…] については、降順に並べ替える必要があります。そしてなんと、私たちは問題の答えを見つけました。

例：

1, 2, 4, 3 => k = 3, x = 4 -> Ans = 1, 2, 3, 4

1, 2, 5, 5, 3, 4 => k = 4, x = 6 -> Ans = 1, 2, 5, 4, 5, 3

Java コード:

public void prevPermutation(int[]data){
     for(int i = data.length - 2; i >= 0; i--){
         if(data[i] > data[i + 1]){
            int index = i + 1;
            for(int j = i + 2; j < data.length; j++){
                if (data[j] > data[index] && data[j] < data[i]){
                     index = j;
                }
            }
            int tmp = data[i];
            data[i] = data[index];
            data[index] = tmp;
            sortDescending(data, i + 1, data.length);
            break; 
         }
     }

}
public void sortDescending(int[]data, int from, int to){
     int[]copy = Arrays.copyOfRange(data, from, to);
     Arrays.sort(copy);
     for(int i = from; i < to; i++){
          data[i] = copy[to - i - 1];
     }         
}

時間計算量: O (n log n) (n は桁数)。

ライブデモ: https://ideone.com/ZLaSa0

わずかに改良されたバージョン: O (n) 時間の計算量 https://translate.google.com/translate?hl=ja&sl=en&tl=ja&u=https://ideone.com/RvmymX