金山软件面试题
1. 一个数组{3，4，5，6，3}，请输出这个数组的全排列，比如34563、43563、33456...。
2. 编写程序编写程序编写程序编写程序：在O(n)时间复杂度内从数组array[0..n-1]中找出第k个最小的元素。 说明：算法可以对array中的元素进行排序。
3. 综合考察综合考察综合考察综合考察：银行有个存有n个用户编号的文件，每个数都小于n，其中n=10的7次方。每个编号都不重复。 输出：n个数升序排列。约束条件：内存最多有2兆的空间，运行时间复杂度为O（n）
[解决办法]

引用:

7.某天晚上，有4个人要过桥，都在桥的一边，有一个手电筒，一次最多过两个人，
不管几个人过桥都要手电筒，每个人过桥时间为1,2,5,10.请问他们最快多久可以过桥，
用什么方案？

17分钟 1 & 2 = 2分 1返回 +1分
5 & 10 = 10分 2返回 +2分
1 & 2 = 2分

2+1+10+2+2 = 17分
[解决办法]
2.编写程序：在O(n)时间复杂度内从数组array[0..n-1]中找出第k个最小的元素。
说明：算法可以对array中的元素进行排序。
解题思路：
因为要求时间复杂度为o(n),所以没有考虑交换排序算法模式，而是选用线性排序模式，选用了计数排序算法。
#include<iostream>
#include<stdio.h>

void output(int a[],int length)
{
for(int i=0;i<length;++i)
{
std::cout.width(2);
std::cout<<a[i];
}
std::cout<<std::endl;
}

void countsort(int a[],int length,int key)
{
int max;
int i;

max = a[0];
for(i=0;i<length;++i)
{
if(max<a[i])
{
max = a[i];
}
}

int lp = max+1;
int *p = (int *)malloc(sizeof(int)*lp);
int *b = (int*)malloc(sizeof(int)*length);
memset(p,0,sizeof(int)*lp);

for( i = 0;i<length;++i)p[a[i]]++; //O(n)

for(i=1;i<lp;++i)p[i]=p[i]+p[i-1]; //O(k)

for(i=length-1;i>=0;--i) //O(n)
{
b[p[a[i]]-1] = a[i];
p[a[i]]--;
}

//output(b,length);
std::cout<<b[key-1]<<std::endl;

free(b);
free(p);
p=b=NULL;
}

int main()
{
int a[10] = {5,2,6,3,1,9,6,7,8,10};
countsort(a,10,3);

return 0;
};

[解决办法]
3. 综合考察：银行有个存有n个用户编号的文件，每个数都小于n，其中n=10的7次方。每个编号都不重复。 输出：n个数升序排列。约束条件：内存最多有2兆的空间，运行时间复杂度为O（n）
解题思路：
10000000个数，一个数占一位，1250000个字节，312500个unsgined int ,大概需要1.2M内存。
整个程序我看了一下是2.67M左右，大于2M，有没有人更好的方法？

#include <iostream>

#include <fstream>

#define MAXSUM 312500

const std::size_t s[32]={
0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,0x00000080,0x00000100,0x00000200,
0x00000400,0x00000800,0x00001000,0x00002000,0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,
0x00100000,0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x08000000,0x10000000,0x20000000,
0x40000000,0x80000000
};

void Magnanimitysort()
{
std::size_t *a;
std::size_t b=1;
std::size_t n=0;
std::size_t n1=0,n2=0;

a = (std::size_t*)malloc(sizeof(std::size_t)*MAXSUM);
if(a==NULL)return ;

memset(a,0,sizeof(std::size_t)*MAXSUM);

std::ifstream file("e://acm.txt");
if(!file)
{
std::cout<<"打开文件失败!"<<std::endl;
return ;
}

std::ofstream file2("e://acm2.txt");
if(!file2)
{
std::cout<<"打开文件失败!"<<std::endl;
return ;
}

while(!file.eof())
{
file>>n;
n1=n/32;
n2=n%32;

b=1;
a[n1] = a[n1]
[解决办法]
b<<n2;
}

file.close();

for(b=0;b<MAXSUM;++b)
{
if(a[b]==0)break;

std::size_t i=0;
for(i=0;i<32;i++)
{
std::size_t t = a[b]&s[i];
if( t>0 )
{
//std::cout<<i+b*32<<"\n";
file2<<i+b*32<<"\n";
}
}
}
file2.close();
free(a);
a=NULL;
}

int main()
{
//createfile();
Magnanimitysort();

return 0;
};