金山软件面试题解决方案

金山软件面试题
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;

金山软件面试题解决方案

相关推荐