没有合适的资源？快使用搜索试试~ 我知道了~

文库首页行业互联网十年大厂Java笔试面试题及答案

十年大厂Java笔试面试题及答案

Java面试笔试题

Java笔试题及答案

需积分: 50 7 下载量 187 浏览量 2021-03-12 20:48:33 上传评论收藏 31KB DOCX 举报

温馨提示

试读

15页

适合Java开发面试

资源详情

资源评论

资源推荐

 个降序数组，找到最大的  个数 

（版）

假定有  个有序数组，每个数组有  个数字，降序排列，数字类型  位  数值，

现在需要取出这  个数字中最大的  个，怎么做？

解决方法

这里其实有很多解决方法，笨拙的或者巧妙的。这里介绍一个非常不错的方法，使用最大

堆堆排序：

建立大顶堆，维度为数组的个数，这里为 （第一次插入的是每个数组中最大的值，

即第一个元素）。

删除最大堆堆顶，保存到数组或者栈中，然后向最大堆插入删除的元素所在数组的下一

个元素。

重复第  个步骤，直到删除个数为最大的  个数，这里为 

代码：

#include <iostream>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <functional>

using namespace std;

#define ROWS 20

#define COLS 500

int data[ROWS][COLS];

void CreateData()

{

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

{ for(int j=0; j<COLS;j++)

{

data[i][j] = rand(); //生成随机元素

}

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

sort(data[i],data[i]+COLS, greater<int>()); //对每一行降序排列

}

struct Node

{

int *p; //指向某个列，因为要放入优先队列中，所以要比较大小，就用结构体

封装了下 bool operator<(const struct Node &node) const

{

return *p < *node.p;

}

};

void OutMinData( int k) {

struct Node arr[ROWS];

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

{

arr[i].p = data[i]; //初始化指针指向各行的首位

}

priority_queue<Node > queue( arr, arr+ROWS ); //使用优先队列，默

认是大堆

for( int i=0; i<k&&i<COLS; i++) //算法核心就是这个循环

{

Node temp = queue.top(); //取出队列中最大的元素

cout << *temp.p << " " <<endl; queue.pop(); //从队列里删除

temp.p++; //对应行的指针后移

queue.push( temp ); //这里面有 log（ROWS）次操作，所以算法的总复

杂度为 O（klog（20））

}

int main()

{

CreateData(); //生成数据

int k=500;

OutMinData( k ); //输出 k 个元素，这里 k 不要大于列数 COL，可以改进，去

掉这个限制，不过会让程序不好懂，就没加

return 0;

}

 寻找数组中第  大的数

1）方法一：堆排序找第 k 大的数，先构建大根堆，求第 k 大的数，就调整 k 次，

然后输出 arr[len-k]位置的数

 !""#$%&

'()""#$*

""#$)""#$*

""#$)'(*

,,构建大根堆并调整  次

-'."!#$""%&

/"!)""'0-,1*2)*11%&

!""""'0-%*

/"!)*3*%&

 !""""'0-11%*

!""""'0-11%*

.4'("!""#""'0-1$%*

!#$""'%&

'()""#$*

/"!)5*3'*)5%&

/!""#$3""#$663'%&

*

/!""#$2'(%&

""#$)""#$*

)*

+''&

"'*

""#$)'(*

(!."0#$"0%&

#$"")' #$&789:+*

)*,,找第  大的数

-'."!""%*

,,输出为 9

2）方法二、快速排序思想，先找数组第 k 大的数，当执行一次 partition 函数

找到 index 下标时，index 左边的数比 arr[index]大，右边的数比 arr[index]小

'&

,,第  小，快速排序寻找一次数字正确位置的下标

"!#$"" -0-%&

'()""#

-'! 3-0-%&

-'! 3-0-66""#-0-$2'(%&

-0-11*

""# $)""#-0-$*

-'! 3-0-66""# $3'(%&

 *

""#-0-$)""# $*

剩余14页未读，继续阅读

内容反馈

CYL_TING

粉丝: 0
资源: 1

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

十年大厂Java笔试面试题及答案

评论0

最新资源

十年大厂Java笔试面试题及答案

评论0

华为等各大厂Java面试笔试题汇总.rar

大厂Java笔试及面试题合集.pdf

互联网大厂Java岗位笔试面试题

【推荐】华为等各大厂Java面试笔试题汇总.zip

大厂java工程师岗位经典笔试面试题

互联网大厂Java工程师面试题及其答案.pdf

大厂的Java面试题分享

Java面试题及答案包含大厂面试真题

1000道互联网大厂Java工程师面试题及答案

Java面试题大厂.zip

某互联网大厂Java面试题-18题（附带答案）

大厂超级详细的Java面试题.zip

2023java面试题大全及答案大厂面试经典问题

Java秋招各大厂笔试面试题.zip

JAVA面试重点话术+常见面试题指南+基础笔试100道+1000道 互联网大厂面试精华

Java大厂面试题练习.zip

Java 秋招各大厂笔试面试题.zip

Java面试题大厂汇总.zip

2019年互联网大厂高频重点面试题第二季（思维导图+视频）

尚硅谷_互联网大厂高频重点面试题（第2季）.xmind

通信大厂java工程师岗位笔试面试题

java最新面试题很全

2019互联网大厂高频重点面试题 （第2季）脑图-完结.txt

Java大厂面试题分类汇总

一线互联网大厂Java面试题

最新大厂Java面试题（上）.pdf

Mysql精选大厂面试题附答案

最新资源

JAVA面试重点话术+常见面试题指南+基础笔试100道+1000道互联网大厂面试精华

2019互联网大厂高频重点面试题（第2季）脑图-完结.txt