26

正の整数 (数字の配列の形式) を指定します。指定された数字の 1 組の数字を入れ替えることができます。取得できる最小の整数を返す必要があります。有効な整数である必要があることに注意してください。つまり、先頭に 0 を含めないでください。

例えば：-

  1. 93561 は 13569 を返します
  2. 596 リターン 569
  3. 10234 は 10234 を返します
  4. 120 リターン 102
  5. 10091 は 10019 を返します
  6. 98761111 は 18761119 を返します

O(n)この問題のアルゴリズムはありますか。私はこれのためにいくつかの方法を考えました:-

  1. 分を見つけます。指定された整数 (0 を除く) の数字 ( minDIgit) を MSB と交換しMSB != minDigitます。の場合MSB==minDigit、次の分を見つけます。桁を変更し、最上位 2 桁以外の桁などと交換します。これはO(n^2)最悪の場合である可能性があります。
  2. array/vectorof digitstd::pairと index を作成し、昇順で並べ替えます (数字の値に従って、数字の値を一致させるために低いインデックスを最初に保持します)。ソートされた配列を反復処理します。MSB を最初の桁と入れ替えます。最小桁に対応するインデックスが MSB である場合、MSB を 1 桁だけ次の最小桁と交換します。次の最小桁に対応する MSB の 1 桁のインデックスがある場合、MSB の 2 桁をこの次の最小と交換します。桁など。これはする必要がありますO(nlog(n))。

誰かがより良いアルゴリズムを提案できますか?

更新 1: 少し考えた後、私が提案した 2 番目のアルゴリズムは完全に正常に機能します (おそらく、個別に処理できるいくつかのコーナー ケースを除く)。さらに、（数字の値に応じて）カウントソートを使用してペア（数字、インデックス）をソートできます。これは時間的に安定したソートO(n)です。私の主張に誤りはありますか？

更新 2: 私の 2 番目のアルゴリズムは機能します (ただし、コーナー ケースと 0 のチェックが増えますO(n)) counting sort。しかし、@ GaborSch が提供する解決策ははるかに簡単なので、アルゴに適切なコードを提供することはあまり気にしません。

4

7 に答える 7

18

準備として、数字をループし、配列 [10] ( と呼びます) (s を含む)内の数字の最後の位置をマークします。それがO(n)です。last0

次に、数字を左から右に繰り返します。各位置について、最後の位置が現在の位置よりも大きい最小の桁を見つけようとします(位置制約)。また、その桁は現在の桁よりも小さくする必要があります。

最初の位置にいる場合は、現在の桁の値 (含まない) までループを開始しますlast(1そうでない場合は から0)。

そのような桁が見つかった場合 (位置の制約に関して)、交換します (そしてループを中断します)。そうでない場合は、次の桁に進みます。コストは最大で O(n*9)、つまり O(n) です。

総コストは O(n) + O(n)*O(9) = O(n) です。

アルゴリズムは例でどのように機能しますか:

93561 ->   it can swap in the first cycle

596   ->   skipping the first cycle, 
           then finds '6' because of the position constraint 
           (comparing position '1' with last[5] = 0, last[6] = 2)

10234 ->   does not find anything because of the position constraint

93218910471211292416 -> finds the last occurrence of '1' to replace '9'

98761111 -> it can swap in the first cycle
            (last[1] = 7, so it will change the last occurrence)

555555555555555555596 -> iterates until the '9', then you skip last[5]
            but finds last[6] as a good swap

120 ->      at pos 0 (1) cannot find a non-zero element less than 1, so skip
            at pos 1 (2) can find 0 on position 2, so we swap

繰り返しますが、ここでは数字に対して 1 回の反復 (データの事前解析用) を行い、次に MSB を見つけるための 1 回の反復を行います。2 番目の反復lastでは、一定サイズ (最大 9) の を反復します。

でループを開始する価値があるときに最小値を追跡することを追加することで、アルゴリズムをさらに最適化できますが、それはlastすでに最適化です。以前のバージョンにはそれが含まれていました。興味がある場合は履歴を確認してください:)

于 2013-06-18T17:34:21.187 に答える
5

右端から配列を反復処理します。右側の数字を最小の数字と最大の数字として保存し、左に移動し始めます。新しい小さい数字にヒットした場合は、それを潜在的な最小の数字と呼びます。左に移動し続けて小さい数を見つけたら、小さい方をポテンシャルにします。より大きな数値を見つけた場合は、最小の int を潜在的に小さくし、最大の桁として大きい方を格納します。最小の桁よりも大きな桁にヒットするたびに、それを新しい最大桁にします。最後にヒットした場合は、最大桁と最小桁を入れ替えます。Pythonの場合（これは機能し、O（n）です）

def swap_max(digits):
    i = len(digits) - 1
    while i > 0:
        if digits[i] == 0:
            i-= 1
        else:
            break
    max_i = i
    min_i = i
    pot_i = i
    z_i   = -1
    nz_i  = i
    i = len(digits) - 1
    while i >= 0:
        if digits[i] > digits[pot_i]:
            max_i = i
            min_i = pot_i
        if digits[i] < digits[min_i] and digits[i] != 0:
            pot_i = i
        if digits[i] == 0 and z_i == -1:
            z_i = i
        if digits[i] != 0 and i > 0:
            nz_i = i
        i -= 1
    if z_i != -1 and max_i != 0 and max_i < z_i:
        min_i = z_i
        i = nz_i
        max_i = i
    elif max_i == min_i and z_i != -1:
        i = nz_i
        if i < z_i:
            min_i = z_i
            max_i = i

    v = digits[min_i]
    digits[min_i] = digits[max_i]
    digits[max_i] = v
    return digits


#TESTING THE FUNCTION
tests =   [93561,596,10234,120,10091,98761111,1001,1010,1103,120,93218910471211292416]
results = [13569,569,10234,102,10019,18761119,1001,1001,1013,102,13218910471211292496]
tests = map(list,map(str,tests))
results = map(list,map(str,results))
for i in range(len(tests)):
    res ="".join(map(str,swap_max(map(int,tests[i]))))
    print res,"".join(results[i])
    if res=="".join(results[i]):
        print "PASSED\n"
    else:
        print "FAILED\n"

これは、すべての例で機能しました。また、メモリ使用量が O(1) であるという利点もあります。

于 2013-06-18T16:54:48.360 に答える