两个无序数组A和B，长度分别是m和n，求中位数，要求时间复杂度O(m+n)，空间复杂度O(1) 
来自：人人网面试题，5分钟出思路，10分钟出代码
分析：乍一看题目，不知道在考什么。
把问题简化下。有一个无序数组，长度m+n，在O（m+n）时间内找出中位数，空间复杂度O（1）。
可以用快速查找在线性时间里找出中位数。
若分布在两个数组里，该怎么找？
是否可以把两个数组看成是一个，当查找到数组边界时，做一次边界判断，跳到另一个数组继续查找。
判断起来有点麻烦，但应该可以实现。欢迎讨论

一个数的整数次幂，是我们在计算中经常用到的，但是怎么可以在 $\mathcal{O}(\log (n))$ 的时间内算出结果呢？
代码框中的代码是一种实现，请分析并填写缺失的代码，求 x^y \mod pxy
modp 的结果。                       
解题思路： 代码填空题
1.y&1: 按位与运算，数字按位与1，如果=1，则数字为奇数，=0数字为偶数
import java.util.*;
public class Main {
    public static int pw(int x, int y, int p) {
        if (y == 0) {
            return 1;
        }
        int res = pw(x,y/2,p)*pw(x,y/2,p)%p;
        if ((y & 1) != 0) {
            res = res * x % p;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int x = cin.nextInt();
        int y = cin.nextInt();
        int p = cin.nextInt();
        System.out.println(pw(x, y, p));
    }
}

（1）如果给你组数：1 2 3 4 5 

（2）如果给出的条件是让你从小到大求出下一个排列，当然就是：1 2 3 5 4

（3）如果再下一个就是：1 2 4 3 5  ；再下一个是：1 2 4 5 3

（4）如果问你求的是下n个排列是什么？你该怎么快速求出呢？？？

当然，在（2）中的答案可以从（1）中的倒数第一位与第二位比较，如果倒数第一位比第二位大，那么交换位置，然后下一个排列就是交换后的了，即：1 2 3 5 4；

然后依次下去用这种思想可以求出下面的排列……

但是你想想每位都要比较判断，如果相等又往前推，依次这样的话，判断语句又多，代码也不会短，你不烦我还烦呢…… ^_^ 嘿嘿，想偷懒就得想个法子解决问题……

所以懒也是有原因的……next_permutation出场的时候就到了……

 

 

使用方法：next_permutation(数组头地址，数组尾地址);若下一个排列存在，则返回真，如果不存在则返回假

举例：

（1）数据数组

 


	
int main()
	
	

	
{
	
	

	
int a[6] = {1, 2, 3, 5, 4};
	
	

	
if (next_permutation(a, a + 5))
	
	

	
{
	
	

	
for (int i = 0; i < 5; i++)
	
	

	
{
	
	

	
cout << a[i] <<' ';
	
	

	
}
	
	

	
}
	
	

	
return 0; 
	
	

	
}
	
输出：1 2 4 5 3;也就是12 3 5 4的下一个排列咯，是不是很快……

 

 

（2）字符串（字母数组）

 


 


	
int main()
	
	

	
{
	
	

	
string str = "abcde"; ///输出下5个排列
	
	

	
int k = 0;
	
	

	
while (next_permutation(str.begin(), str.end()))
	
	

	
///begin()与end()是string类的迭代器
	
	

	
{
	
	

	
k++;
	
	

	
cout << str << endl;
	
	

	
if (k == 5)
	
	

	
{
	
	

	
break;
	
	

	
}
	
	

	
}
	
	

	
return 0;
	
 

 

输出：

abced

abdce

abdec

abecd

abedc

问题又来了，既然next_permutation可以求下一个排列，那有没有函数可以求上一个排列的？当然有啦！就是prev_permutation

用法与next_permutation是一样的。

例：

 


 


	
int main()
	
	

	
{
	
	

	
string str = "abecd";
	
	

	
if (prev_permutation(str.begin(), str.end()))
	
	

	
///begin()与end()是string类的迭代器
	
	

	
{
	
	

	
cout << str << endl;
	
	

	
}
	
	

	
return 0;
	
	

	
}
	
 

输出：abdec;//看上面例子

原网址https://blog.csdn.net/GreatJames/article/details/75150001 

（1）如果给你一组数：1 2 3 4 5 

（2）如果给出的条件是让你从小到大求出下一个排列，当然就是：1 2 3 5 4

（3）如果再下一个就是：1 2 4 3 5  ；再下一个是：1 2 4 5 3

（4）如果问你求的是下n个排列是什么？你该怎么快速求出呢？？？

当然，在（2）中的答案可以从（1）中的倒数第一位与第二位比较，如果倒数第一位比第二位大，那么交换位置，然后下一个排列就是交换后的了，即：1 2 3 5 4；

然后依次下去用这种思想可以求出下面的排列……

 

先说一个题要求按顺序输出一个数组的排列（利用递归：从后到前有序交换的思路）

#include<iostream>
using namespace std;
int arr[5] = { 0,1,2,3,4 };
void swap(int x, int y)//用于交换数组的两个数
{
	int temp = arr[x];
	arr[x] = arr[y];
	arr[y] = temp;
}
int sum = 0;
int resove(int n)//递归函数
{
	if (n == 5)//当尝试对不存在的数组元素进行递归时，标明所有数已经排列完成，输出。
	{
		sum++;
		for (int i = 0; i<5; i++)
			cout << arr[i];
		cout << endl;
		return 0;
	}
	for (int i = n; i<5; i++)//循环实现交换和之后的全排列  
	{//i是从n开始 i=n;swap(n,i)相当于固定当前位置，在进行下一位的排列。
		swap(n, i);
		resove(n + 1);
		swap(n, i);//☆重要的一步：互换完还要还原，保持原有顺序防止重复
	}

}
int main()
{
	resove(0);
	cout << sum;
}

但是比较麻烦，了解STL中的next_permutation()之后可以直接使用函数。

使用方法：next_permutation(数组头地址，数组尾地址);若下一个排列存在，则返回真，如果不存在则返回假

举例：

（1）数据数组

int main()
{
    int a[6] = {1, 2, 3, 5, 4};
    if (next_permutation(a, a + 5))
    {
        for (int i = 0; i < 5; i++)
        {
            cout << a[i] <<' ';
        }
    }
    return 0;
}


输出：1 2 4 5 3;也就是12 3 5 4的下一个排列咯，是不是很快……

 

 

（2）字符串（字母数组）

int main()
{
    string str = "abcde"; ///输出下5个排列
    int k = 0;
    while (next_permutation(str.begin(), str.end()))
        ///begin()与end()是string类的迭代器
    {
        k++;
        cout << str << endl;
        if (k == 5)
        {
            break;
        }
    }
    return 0;


输出：

abced

abdce

abdec

abecd

abedc

问题又来了，既然next_permutation可以求下一个排列，那有没有函数可以求上一个排列的？当然有啦！就是prev_permutation

用法与next_permutation是一样的。

例

int main()
{
    string str = "abecd";
    if (prev_permutation(str.begin(), str.end()))
        ///begin()与end()是string类的迭代器
    {
        cout << str << endl;
    }
    return 0;
}


输出：abdec;//看上面例子