首页 > 代码库 > 完美洗牌&洗牌

完美洗牌&洗牌

完美洗牌问题,给定一个数组a1,a2,a3,...an,b1,b2,b3..bn,把它最终设置为b1,a1,b2,a2,...bn,an这样的。

O(n)的算法,O(n)的空间。

对于前n个数,映射为f(i)=2 * i + 1, 0 <= i < n / 2; 比如0->1, 1->3

对于后n个数,映射为f(i)=2(i - n/2), n / 2 <= i < n; 比如n/2->0, n/2 + 1->2... 并且f(i) =2(i - n/2)=2*i-n=2*i+1-(n+1)=(2*i+1)%(n+1)。

统一起来,映射为f(i) = (2 * i + 1) % (n + 1).

 1 void perfectShuffle1(int arr[], int n) { 2     int* tmp = new int[n]; 3     for (int i = 0; i < n; ++i) { 4         tmp[((i << 1) + 1) % (n + 1)] = arr[i]; 5     } 6     for (int i = 0; i < n; ++i) { 7         arr[i] = tmp[i]; 8     } 9     delete[] tmp;10 }

分治法,O(nlgn)的算法,O(lgn)的空间。

Line 4-11 主要就是处理好数组的一半为奇数的情部分。

当n/4!=0的时候,数组的一半为奇数。此时要将[n/2,n)的数往左移,把第n/2-1个数(前一半的最后一个数)放到末尾,这样,最后两个数就排好了。问题就转化成了数组的一半是偶数的情况。

当数组的一半是偶数时,只需要把前一半的后半部分和后一半的前半部分交换一下,就达到分治的目的了。

 1 void perfectShuffle2(int arr[], int n) { 2     if (n % 2 != 0) return; 3     if (n <= 1) return; 4     if (n % 4 != 0) { 5         int tmp = arr[n / 2 - 1]; 6         for (int i = n / 2; i < n; ++i) { 7             arr[i - 1] = arr[i]; 8         } 9         arr[n - 1] = tmp;10         n -= 2;11     }12     for (int i = 0; i < n / 4; ++i) {13         swap(arr[n / 4 + i], arr[n / 2 + i]);14     }15     perfectShuffle2(arr, n / 2);16     perfectShuffle2(arr + n / 2, n / 2);17 }

主要参考自:http://blog.csdn.net/caopengcs/article/details/10176093, 里面提到的第三种解法没去看,感觉面试不会考就先不费力去理解了。

洗牌的问题就比较简单,其实相当于从数组中随机选出m个数,见之前的博文。只不过这里m=n而已。

1 void shuffle(int arr[], int n) {2     srand(time(NULL));3     for (int i = 0; i < n; ++i) {4         swap(arr[i], arr[i + rand() % (n - i)]);5     }6 }

这个和网上提到的FisherYates洗牌算法的原理是一样的。

完美洗牌&洗牌