|
| 1 | +/** |
| 2 | +第二题，给一组String[](容量<10000)，求每一个String(长度<100)在其自己的 |
| 3 | +Permutation Sequence中的序号 |
| 4 | +
|
| 5 | +Input: // String[] |
| 6 | +cab |
| 7 | +babc |
| 8 | +
|
| 9 | +Output: //返回 int[], index starting from 0 |
| 10 | +4 //{abc, acb, bac, bca, 【cab】, cba} |
| 11 | +3 //{abbc, abcb, acbb, 【babc】,.....} |
| 12 | +
|
| 13 | +//注意，String内有重复的Character，但 Permutation Sequence 只保留distinct记录 |
| 14 | +
|
| 15 | +
|
| 16 | +Solution: |
| 17 | +对于每一个字母, 找到在排序后的字符串中的位置 |
| 18 | +比如cab，源字符串排序abc |
| 19 | +c -> 2 (remove c, source string becomes "ab") |
| 20 | +a -> 0 (remove a, source string becomes "b") |
| 21 | +b -> 0 (remove b) |
| 22 | +所以在目标字符串的位置就是2*2! + 1*0! + 0*0! = 4 |
| 23 | +
|
| 24 | +第二个有重复的例子，就选取最左边的位置（比如babc排序是abbc，第一次b出现的位 |
| 25 | +置为1） |
| 26 | +1*3!/2! + 0*2! + 0*1! + 0*0! |
| 27 | +
|
| 28 | +general solution: |
| 29 | +1, In each pass, get the first char c of the string. |
| 30 | +2, Get the index of c in sorted char sequence of all chars in string, assume it's n. |
| 31 | +3, Assume the number of c in string is k. |
| 32 | +4, Assume the current length of string is l, then res+=n*(l-1)!/k!. |
| 33 | +5, Get rid of all c in string without changing the relative position of other chars, then |
| 34 | +repeat the above process. |
| 35 | +
|
| 36 | +Note: in each pass, l-1 is how many positions we can have other than the head position, |
| 37 | +and n is how many chars other than c can be put at the head. |
| 38 | +
|
| 39 | +If there are duplicate chars, then we also need to get the number of c in string, assumes it's k. |
| 40 | +Then in step3, res+=n*(l-1)/k! |
| 41 | +
|
| 42 | +Time complexity: O(n^2logn) |
| 43 | +*/ |
| 44 | + |
| 45 | +using System; |
| 46 | +using System.Collections.Generic; |
| 47 | +using System.Linq; |
| 48 | +public class Test |
| 49 | +{ |
| 50 | + //Get original index of s in its permutations sequence |
| 51 | + public static int GetIndexPermutation(string s){ |
| 52 | + int[] map = new int[256]; //map letter to occurence |
| 53 | + foreach(char c in s) |
| 54 | + map[c]++; |
| 55 | + char[] array = s.ToCharArray(); |
| 56 | + int res = 0; |
| 57 | + while(array.Length>1){ |
| 58 | + int l = array.Length-1; //get current length-1 |
| 59 | + int k = map[array[0]]; //get occurence of current first char |
| 60 | + int n = GetOriginalIndex(array); //get original index |
| 61 | + res+=n*GetFactorial(l)/GetFactorial(k); //calculate |
| 62 | + array = array.Where(y=>y!=array[0]).ToArray(); //remove all array[0] |
| 63 | + } |
| 64 | + return res; |
| 65 | + } |
| 66 | + |
| 67 | + //Get original index of the first char in s |
| 68 | + private static int GetOriginalIndex(char[] a){ //O(nlogn) |
| 69 | + char target = a[0]; |
| 70 | + char[] array = new char[a.Length]; |
| 71 | + Array.Copy(a,0,array,0,a.Length); //copy a to array |
| 72 | + Array.Sort(array); |
| 73 | + //return the first occurence index of target in array |
| 74 | + return Array.IndexOf(array, target); |
| 75 | + } |
| 76 | + |
| 77 | + //Get n! |
| 78 | + private static int GetFactorial(int n){ //O(n) |
| 79 | + int res=1; |
| 80 | + for(int i=n;i>=1;i--) |
| 81 | + res*=i; |
| 82 | + return res; |
| 83 | + } |
| 84 | + |
| 85 | + public static void Main() |
| 86 | + { |
| 87 | + Console.WriteLine(GetIndexPermutation("ba")); |
| 88 | + Console.WriteLine(GetIndexPermutation("dabc")); |
| 89 | + Console.WriteLine(GetIndexPermutation("babc")); |
| 90 | + } |
| 91 | +} |
0 commit comments