百度面试题——需找下一个排列(Find next permuation, POJ 1883)
百度面试题——需找下一个排列(Find next permuation, POJ 1883)
面试中关于排列的题目还是蛮常见的,之前有个同学面百度,就遇到了一个排列题目,分享一下。
题目描述:
给你一个数组,如果是按照数字的大小排序,那么请你输出当前数组的下一个排列是什么
例如, 下面的数据,就是按照排列序生成的四组数据。
3 1 2 4 5
3 1 2 5 4
3 1 4 2 5
3 1 4 5 2
虽然有个函数叫next_permutation, 不过做OJ还好,面试这个一定不行啦,所以还是自己分析一下。
分析:
我们用字典序的排列生成方法:
生成给定全排列的下一个排列
所谓一个的下一个就是这一个与
下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。
算法分三个步骤:
一般而言,设P是[1,n]的一个全排列。
1. P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn
j=max{i|Pi<Pi+1},k=max{i|Pi>Pj}
2. 对换Pj,Pk,将Pj+1…Pk-1PjPk+1…Pn翻转,
3. P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个。
代码如下:
- Memory: 168K Time: 469MS
- Language: C++ Result: Accepted
- Source Code
- #include<stdio.h>
- #include <memory.h>
- void swap( int &a, int &b)
- {
- a = a ^ b;
- b = a ^ b;
- a = a ^ b;
- }
- bool GetNextPermutation(int a[], int size)
- {
- int m = size - 1;
- int i,j;
- while(m > 0 && a[m-1] > a[m]) // step 1
- {
- m--;
- }
- //in this case, the current permutation is the last
- if(m == 0) //
- {
- for( i = 0, j = size - 1; i < j; i++, j--)
- {
- swap(a[i], a[j]);
- }
- return false;
- }
- for( j = size - 1; j > m - 1; j--)//step 2
- {
- if(a[j] > a[m-1])
- {
- swap(a[j], a[m-1]);
- break;
- }
- }
- for( i = m, j = size - 1; i < j; i++, j--)//step 3
- {
- swap(a[j], a[i]);
- }
- return true;
- }
- void printArray(int a[], int size)
- {
- int i;
- for( i = 0; i < size; i++)
- {
- if( i == 0)
- {
- printf("%d", a[i]);
- }
- else
- {
- printf(" %d", a[i]);
- }
- }
- printf("\n");
- }
- int main()
- {
- int nSize;
- int a[1024];
- int ncase;
- scanf("%d", &ncase);
- int n,k;
- while(ncase--)
- {
- scanf("%d%d", &n, &k);
- for( int i = 0; i < n; i++)
- {
- scanf("%d", &a[i]);
- }
- while(k--)
- {
- GetNextPermutation(a, n);
- }
- printArray(a, n);
- }
- return 0;
- }
|
评论暂时关闭