通過交換第一個整數在置換之間移動的算法

Question

今天我被問了一個有趣的面試問題。假設你有前n個整數A（例如13425）和另一個置換B（例如43125）的置換。我們必須從第一個置換移動到第二個置換，只需將索引1到n-1處的值與索引0處的值交換即可。

換句話說，我們可以將序列13425中的索引0和1交換爲31425.但是我們不能在序列13425中交換索引2和3以產生13245.

最後，在這些交換之後，我們必須進行排列B.任何人都可以想出一個運行時間比O（ N^2）？

Answer 1

是的，有存在O（N）解決方案，這裏是Java實現：

private static void swap(int[] idx, char[] c, int i) { 
    idx[c[i]-'0'] = 0; 
    idx[c[0]-'0'] = i; 

    char tc = c[0]; 
    c[0] = c[i]; 
    c[i] = tc; 
} 

public static void permutation(final String from, final String to) { 
    final int[] idx = new int[10]; 

    final char[] c1 = from.toCharArray(); 
    final char[] c2 = to.toCharArray(); 

    for (int i = 0; i < c1.length; i++) { 
     idx[c1[i] - '0'] = i; 
    } 

    for (int i=(c1.length-1); i>=0; i--) { 
     if (c2[i] != c1[i]) { 
      final int charIdx = idx[c2[i]-'0']; 
      if (charIdx != 0) { 
       // move char to index 0 
       swap(idx, c1, charIdx); 
      } 
      // move char from 0 to i; 
      swap(idx, c1, i); 
     } 
    } 
}