当前位置:编程学习 > 网站相关 >>

阿里巴巴笔试题目妙解(接示本质的解法)

 
阿里巴巴有如下的笔试题目:
 
有一个神奇的数组,其中的第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)的时间
 
 
 
 
解完.
 
 
补充:综合编程 , 其他综合 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,