百度面试题——需找下一个排列（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…Pnj=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（" "）;
}
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;
}

网易杭州研究院实习面试题和答案百度面试题 --- 锦标赛排序相关资讯互联网百度百度面试题

30亿网民坐稳啦！互联网之门将要换（今 06:51）
互联网迎来“独立日”？（03月21日）
互联网让我们变聪明了？（11/13/2015 07:53:43）

互联网从开放走向封闭（06月20日）
全球首个互联网网页上线 25 周年（12/21/2015 13:40:02）
古巴的Netflix、Hulu和Spotify不在（09/28/2015 07:00:59）

本文评论查看全部评论（0）