MyException - 我的异常网
当前位置:我的异常网» Java Web开发 » 最近遇到一个笔试题,求高手解决!解决方案

最近遇到一个笔试题,求高手解决!解决方案(3)

www.MyException.Cn  网友分享于:2013-01-29  浏览:26次

std::sort( ResArr, ResArr + RES_ARR_SIZE, std::greater_equal() );

//最小元素索引

unsigned int MinElemIdx = RES_ARR_SIZE - 1;

//可能产生交换的区域的最小索引 

unsigned int ZoneBeginIdx = MinElemIdx;

//遍历后续的元素

for( unsigned int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; ++i )

{

//这个后续元素比ResArr中最小的元素大,则替换。

if( BigArr[i] > ResArr[MinElemIdx] )

{

ResArr[MinElemIdx] = BigArr[i];

if( MinElemIdx == ZoneBeginIdx )

--ZoneBeginIdx;

//查找最小元素

unsigned int idx = ZoneBeginIdx;

unsigned int j = idx + 1;

for( ; j < RES_ARR_SIZE; ++j )

{

if( ResArr[idx] > ResArr[j] )

idx = j;

}

MinElemIdx = idx;

}

}

}

经过测试,同样情况下solution_4用时约1.8秒,较solution_3效率略高,总算不负一番努力
 

------解决方案--------------------
1.取前十个数组成长度为10的数组
2.对剩余的数做循环,依次插入,然后对十一个数做排序删除之最小的一个,然后坐下一次循环。
3.最后得到十个数。
(不考虑十亿个数的存放位置)
------解决方案--------------------
既然是笔试,当然是概念题了,10亿个浮点数不知道JAVA占用多少字节,C/C++是3.7GB大小,既然存在3.7GB的数组,那么内存就不用管了,分成1千万一组,那就是100组,于是开100个线程,每线程100万的排序,不管用什么排序法,谁最快用用谁,100个线程排完了,就剩10000个元素的数组了,这10000个元素的数组你想怎么排就怎么排
------解决方案--------------------
1、首先至少有一个循环,这个肯定不能少
2、因为只有10个数,因此用数组实现其实效率并不比链表慢,因为链表也同样存在指针复制的操作。

c++ 实现
C/C++ code

#include "stdafx.h"
#include "iostream"

using namespace std;

class CLoopArray
{
private:
    float _dat[10];
public:
    CLoopArray()
    {
        for(int i=0;i<10;i++)
            _dat[i]=0;
    }

    //插入值,如果大于某个已有值,则插入,否则不插入
    void InsertValue(float value)
    {
        if(value <= _dat[9])return;

        for(int i=0;i<9;i++)
        {
           if(_dat[i] < value)
           {

               for(int j=9;j>i;j--)
               {
                   _dat[j] = _dat[j-1];
               }
               _dat[i]= value;
               break; //跳出循环
           }
        }
    }

    //取对应值
    float& operator[](int index)
    {
        if( (index >=0) && (index <10))
        {
            return _dat[index];
        }
    }
};


int _tmain(int argc, _TCHAR* argv[])
{
    CLoopArray la;

    float v,v2;
    for(int i=0;i<10000000000;i++)
    {
        v2 = rand();
        if(v2 == 0) v2 =1; //防止除零错误
        v = rand()/ v2;
        la.InsertValue(v); 
    }

    for(int i=0;i<10;i++)
    {
        cout << la[i] <<endl;
    }
    return 0;
}

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有