阿里巴巴有如下的笔试题目:
有一个神奇的数组,其中的第i个元素在排序之后的位置位于[i-k, i+k]之间(k序的).试写算法把一个k序数组排序,要求最快.
解法,
显然有以下几个子序列:
X[0], X[k+1], X[2(k+1)], X[3(k+1)]......
X[1],X[k+1+1],X[2(k+1)+1],X[3(k+1)+1]......
........................
X[k],X[k+1+k],X[2(k+1)+k],X[3(k+1)+k]......
这k+1个子序列是已经排序好的,剩下的任务是把其归并
有两种方法:
方法一,
普通的merge,与把两个数组归并一样的思想,则复杂度为O(nk)
方法二
用败者树,则合并一个元素要LogK的时间,合并n个元素要O(nlogk)的时间
解完.
分享到:
相关推荐
ccf历年题目 炉石传说个人简单解法,基础容器运用。ccf历年题目 炉石传说个人简单解法,基础容器运用。ccf历年题目 炉石传说个人简单解法,基础容器运用。ccf历年题目 炉石传说个人简单解法,基础容器运用。ccf历年...
雅虎笔试题目 1、给定字符串A 和B, 输出A 和B 中的最大公共子串。 比如A="aocdfe" B="pmcdfa"则输出"cdf" 解法一: #include #include #include char *commanstring(char shortstring[],char longstring[]) { int i,...
新数通 HCIE3.0 LAB完整版【拓扑+TS+TAC+解法】解法题库新增论述题HCIE笔试题库,同时赠送ENSP软件,用于2022年6月底HCIE数通笔试及LAB实验考试。 1、HCIE数通笔试背过里面题库去考全部通过 2、HCIE LAB拓扑及解法,...
华为LAB 3.0实验题目解法
第三章 解线性方程组的直接解法
利用excel进行线性优化。有题目有解法有答案。题目是经济类的
2016 年 杭电 笔试 第二题 Ruby解法
Delta型并联机器人运动学正解 几何解法pdf,并联机器 人运 动学正 解的封闭解 问题到 目前 为止没有得 到全面 解决, 常用 的解决方 案是采 用基于 代 数万 程组 的数值解法 , 该 方 法 不 足 之 处是推导过程复杂 , ...
考试类精品-- ~南京大学计算机系暑期夏令营上机试题(根据博客上收集的题目还原题目并给出自己的解法版本,仅供参考学习)
我博客中文章经典算法题目及思路解法总结的ppt,博客中的每个问题都在ppt中有详细的讲解,通过掌握这些算法,可以提高你的思维能力。
偏微分方程数值解法 李荣华偏微分方程数值解法 李荣华偏微分方程数值解法 李荣华
微分方程数值解法 一书中主要习题解答 及其习题拓展,纯手工录入,公式清晰,步骤清晰
微分方程数值解法 详细描述了如何通过数值计算求解微分方程
运筹学匈牙利解法解指派问题C语言源代码.此代码可以完成人与任务数量相等与不等的情况
迭代解法数值精度高,但是只能收敛到多解中的一个解,无法同时得到全部可行解;闭式解法的优点是可以一次得到全部可行解,但是现有算法在数值精度和数值稳定性上要逊于迭代解法。针对以上问题,以P3P问题为研究对象...
matlab 解偏微分方程 数值解法 pdf
N皇后的快速解法以及同理可解的问题,值得看看啊。
此资源为PDF格式,内容不为图片,而是可以复制的文字加图形、公式。
ccie sec v4 过人版本解法