迅雷二笔试题

二.求一个包含1亿个数的数组，找出最大的1000个。

void find_max_data(int *source_data, int *max_data)

source_data:指向包含一亿个数的数组

max_data:指向查找到的最大的1000个数的数组

效率越快越好，使用额外空间越小越好！

 

下面是我在考试时想到的答案：

#include <stdio.h>

/*在每一个数组里面查找最大的数并返回
ptr:是指向要查找数组的首地址
*/
#define INT_MIN 0
#define SOURCE_NUM  10e8
#define DEST_NUM  1000
#define NUM_OF_GROUP 10e5

int find_max_in_array(int*ptr)
{
    int max;
    int i, flag;

 i = 0;
 max = ptr[0];
 for (i = 1;i < NUM_OF_GROUP; i++)
 {
  if (max < ptr[i])
  {
   max = ptr[i];
   flag = i;
  }
 }
  ptr[flag] = INT_MIN;
  
 return max;
}

/*从给的含有1亿数组元素中，找到最大的1000个，原数组是source_data，
找到最大的一千个数组存到dest_data中
source_data：原数组
max_data：查找到的元素数组*/
void find_max_data(int *source_data, int *max_data)
{
 int i,j, max;
 int flag = 0;
 int temp_max_data[DEST_NUM];
 int *ptr = source_data;

 for (i = 0; i < DEST_NUM; i++)
 {
  temp_max_data[i] = find_max_in_array(ptr + i * NUM_OF_GROUP);
 }

 j = 0;
 while (j != DEST_NUM)
 {
  i = 0;
        max = temp_max_data[0];
  for (i = 1; i < DEST_NUM; i++)
  {
   if (max < temp_max_data[i])
   {
    max = temp_max_data[i];
    flag = i;
   }
  }
  max_data[j] = max;
  j++;

  temp_max_data[flag] = find_max_in_array(ptr + flag * NUM_OF_GROUP);
 }
}

测试代码：在电脑上不能建立1亿的数组，建立含有1000个元素的数组，找到最大的十个。所以上面SOURCE_NUM    1000            DEST_NUM   10       NUM_OF_GROUP   100

int main()
{
    int source[1000];
 int dest[10];
 int i;

 for (i = 0; i< 1000;i++)
 {
  source[i] = i;
 }
 find_max_data(source,dest);
 for (i =0;i<10;i++)
 {
  printf("%d   ",dest[i]);
 }
 printf("\n");
 return 0;
}

后来我算了一下效率，找到最大的1000个数要查找的次数：1亿 + 1000 * （10e5  + 10e3） = 2亿多一点。我认为还可以。

不知道有没有更高的。如果有的话，希望指教。

被迅雷鄙视了，有些伤心，其实挺想去迅雷的。失败了爬起来，被一个公司鄙视了，再投两公司，不懈努力找工作！