通过交换第一个整数在置换之间移动的算法

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); 
     } 
    } 
}