import java.util.Arrays;
/**
* 最早是在陈利人老师的微博看到这道题:
* #面试题#An array with n elements which is K most sorted,就是每个element的初始位置和它最终的排序后的位置的距离不超过常数K
* 设计一个排序算法。It should be faster than O(n*lgn)。
*
* 英文原题是:
* Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time.
* For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.
*
* 微博里面的回复提到这道题的另一个表述:
* @castomer:回复@华仔陶陶:今年百度校园招聘笔试题目我遇到了一道题和这个基本一样。“
* 一个已经排序好的很大的数组,现在给它划分成m段,每段长度不定,段长最长为k,然后段内打乱顺序,请设计一个算法对其进行重新排序”
*
* 两种解法:
* 1、插入排序,时间复杂度是O(n*k)
* 由于“K most sorted”,寻找位置时最多只会寻找k位,因此复杂度从最坏情况的O(n*n)下降到O(n*k), 但插入排序没有充分利用“K most sorted”这个条件
* 2、最小堆
* @castomer 认为堆的大小是k
* 这要看k most sorted怎么理解了
* 例如,如果对于{4, 3, 2, 1}认为k=3,那么堆的大小就应该是4。因为如果取3的话,第一次最小堆{2, 3, 4}排序后取出最小值2,第二次最小堆排序后取出最小值1,2排在1前面,显然不合理
*
* 最小堆的时间复杂度是O(k) + (n-k) * O(lgk):
* 建堆:O(k),k为堆的大小
* 堆排序:(n-k) * O(lgk)
*
*/
public class KSortedArray {
public static void main(String[] args) {
int k = 3;
int[] array = {2, 6, 3, 12, 56, 8};
insertSort(array);
minHeapSort(array, k);
}
public static void insertSort(int[] arrayToSort) {
//...略去输入合法性检查
//复制数组,不影响原数组
int len = arrayToSort.length;
int[] array = new int[len];
System.arraycopy(arrayToSort, 0, array, 0, len);
for (int i = 1; i < len; i++) {
int itemToInsert = array[i];
while(i > 0 && itemToInsert < array[i - 1]) {
array[i] = array[i - 1];
i--;
}
array[i] = itemToInsert;
}
System.out.println(Arrays.toString(array));
}
public static void minHeapSort(int[] arrayToSort, int k) {
int len = arrayToSort.length;
int[] array = new int[len];
System.arraycopy(arrayToSort, 0, array, 0, len);
int[] sortedArray = new int[len];
int[] heapValues = new int[k + 1];
System.arraycopy(array, 0, heapValues, 0, k + 1);
MinHeap heap = new MinHeap(heapValues);
//将剩下的元素陆续推入堆里,并“吐”出最小值
int j = 0;
for (int i = k + 1; i < len; i++) {
sortedArray[j++] = heap.getRootValue();
heap.replaceRootValueWith(array[i]);
heap.reheap();
}
//没有更多元素进入了,此时剩下k个元素,堆不断收缩,直至为0
//事实上这个while循环可以并入上面的for循环
while (j < len) {
sortedArray[j++] = heap.getRootValue();
heap.minimize();
}
System.out.println(Arrays.toString(sortedArray));
}
}
/**
* 最小堆,只将本次排序中调用到的方法声明为public
*/
class MinHeap {
private int[] values;
private int lastIndex;
public MinHeap(int[] values) {
init(values);
}
public void reheap() {
reheapCore(0, values.length - 1);
}
public int getRootValue() {
return values[0];
}
public void replaceRootValueWith(int newRootValue) {
values[0] = newRootValue;
}
public void minimize() {
if (lastIndex > 0) {
this.replaceRootValueWith(values[lastIndex]);
lastIndex--;
this.reheapCore(0, lastIndex);
}
}
private void init(int[] values) {
int size = values.length;
this.lastIndex = size - 1;
this.values = new int[size];
System.arraycopy(values, 0, this.values, 0, size);
int lastIndex = size - 1;
int lastRootIndex = getRootIndex(lastIndex);
for (int rootIndex = lastRootIndex; rootIndex >= 0; rootIndex--) {
reheapCore(rootIndex, lastIndex);
}
}
private void reheapCore(int rootIndex, int lastIndex) {
if (!(isValidIndex(rootIndex) && isValidIndex(lastIndex))) {
System.out.println("invalid parameters");
return;
}
int orphan = values[rootIndex];
int leftIndex = getLeftIndex(rootIndex);
boolean done = false;
while (!done && leftIndex <= lastIndex) {
int rightIndex = getRightIndex(rootIndex);
int smallerIndex = leftIndex;
if (rightIndex <= lastIndex && values[rightIndex] < values[leftIndex]) {
smallerIndex = rightIndex;
}
if (values[smallerIndex] < values[rootIndex]) {
swap(values, smallerIndex, rootIndex);
rootIndex = smallerIndex;
leftIndex = getLeftIndex(rootIndex);
} else {
done = true;
}
}
values[rootIndex] = orphan;
//System.out.println(Arrays.toString(values));
}
private int getLeftIndex(int rootIndex) {
return rootIndex * 2 + 1;
}
private int getRightIndex(int rootIndex) {
return rootIndex * 2 + 2;
}
private int getRootIndex(int childIndex) {
return (childIndex - 1) / 2;
}
private boolean isValidIndex(int index) {
return index >=0 && index < values.length;
}
private void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
分享到:
相关推荐
百度笔试题之数组差值(题目与源码) ********************************* 给定一个长度为n并且只含有非负整数的数组A,显然这个数组一共有n*(n+1)/2个区间(每个区间至少有一个元素)。给定m个查询值K,对于每个...
百度笔试题 百度 笔试题 百度 笔试题
百度笔试题百度笔试题百度笔试题百度笔试题百度笔试题百度笔试题
百度笔试题大全 百度笔试题大全 百度笔试题大全 百度笔试题大全 百度笔试题大全
名企面试笔试真题:TI 笔试题
百度笔试题,一套完整的百度笔试题,有要应聘百度的兄弟不要错过。
百度历年笔试题百度历年笔试题百度历年笔试题百度历年笔试题
C++笔试题 Sony笔试题 几道题目及自做答案 北电 普天C++笔试题 我所收集的intel比试题 面试题 2005年腾讯招聘 微软 微软亚洲技术支持中心面试题目 微创笔试题目(微创,微软在中国的合资公司) Intel笔试面试题目 ...
百度的历年笔试试题,很齐全,大家有兴趣可以下载下来做做,一定有好处。
一套百度的笔试题,蓝色部分为参考答案 (本资源来自互联网)
2007百度笔试题.txt
百度笔试题 这个不用多说了吧,学计算机的百度应该算是比较向往的地方了
金山笔试题:涉及C++...及一些算法设计技术.....金山笔试题:涉及C++...及一些算法设计技术.....金山笔试题:涉及C++...及一些算法设计技术.....
百度最全笔试题
百度笔试题---数据库百度笔试题---数据库百度笔试题---数据库百度笔试题---数据库
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
本资源为不定项数组的输入方法,利用数据结构vector实现,内有详细的C++代码,经常在算法竞赛或是通信/互联网公司(尤其是牛客网笔试题,如华为、腾讯、阿里)笔试题中用到,欢迎大家下载!
php笔试题 百度
百度网上笔试题及答案 用C语言实现一个revert函数,它的功能是将输入的字符串在原串上倒序后返回。 2 编程: 用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove函数的功能是拷贝src...