在未知长度的超大数组中线性时间内查找第k大的元素

O(n)意味着存在一个常数a,使得它等于an,于是把上面式子求和后化简就有：

```import java.util.Random;

public class SearchKthElement {
private int[] array = null;
private int elementPos = -1;
private int[] twoKBuffer = null;

public SearchKthElement(int[] arr, int k) {
if (arr.length < k) {
throw new IllegalArgumentException("k can not bigger than the length of array!");
}

this.array = arr;
this.elementPos = k;
//分配2k缓冲区
this.twoKBuffer = new int[2*k];

streamElementFromArray();
}

private int  findElementInBuffer(int begin, int end, int k) {
if (k > end - begin) {
System.out.println("begin : " + begin + " end: " + end + " k:" + k);
throw new IllegalArgumentException("k in not in valid range");
}

//如果数组所有元素重复，那么返回其中任何一个元素
int v = twoKBuffer[begin];
int count = 0;
for (int i = begin+1; i <= end; i++) {
if (twoKBuffer[i] == v) {
count++;
}
}
if (count == end - begin ) {
return twoKBuffer[0];
}

Random rand = new Random();
int pos = begin + rand.nextInt(end+1 - begin);
int P = twoKBuffer[pos];
//把小于P的元素搬到左边，大于P的元素搬到右边
int b = begin, e = end;
int posOfP = -1;
while (b < e) {
if (twoKBuffer[b] < P ) {
b++;
continue;
}

int temp = twoKBuffer[b];
twoKBuffer[b] = twoKBuffer[e];
twoKBuffer[e] = temp;
if (twoKBuffer[e] == P) {
posOfP = e;
}
e--;
}
/*
* b 和 e 交汇时他们指向的元素可能小于P，为了确保e指向的元素大于等于P，如果此时e指向的元素小于P,那么就要把e往后挪一位
*/
if (twoKBuffer[e] < P) {
e++;
}

/*
* 把元素P放在左右两部分元素的分界线上，也就是数组形成如下形式:
* |********|********|
*    <P   P   >=P
* 左边部分小于P,中间是元素P,右边是大于等于P的元素
*/
//把P的值放到位置e上
if (posOfP != -1) {
int temp = twoKBuffer[e];
twoKBuffer[e] = twoKBuffer[posOfP];
twoKBuffer[posOfP] = temp;
}

/*
* 把P左右两边的元素分别打印出来，主要出于调试目的
*/
System.out.println("Pivot is : " + P);
System.out.println("first half:");
for(int i = begin; i < e; i++) {
System.out.print(" " + twoKBuffer[i]);
}
System.out.println("\nsecond half: ");
for (int j = e; j <= end; j++) {
System.out.print(" " + twoKBuffer[j]);
}
System.out.print("\n");

if (e - begin == k) {
//如果P前面包括它自己有k个元素，那么P在当前数组是第k大的元素
return twoKBuffer[e];
}

if (e - 1 - begin >= k) {
//如果P前面有多于k个元素，那么第k大的元素在P的左边部分
return findElementInBuffer(begin, e - 1, k);
} else {
//如果P左边的元素有t个，t < k, 那么第k大的元素在P的右边，它是右边数组第k-t大的元素
k = k - (e - begin);
return findElementInBuffer(e, end, k);
}
}

private void streamElementFromArray() {
int start = 0;
int n = 0;
int count = 0;

try {
/*
* 依次从大数组中读入元素，然后放入2k缓冲区，如果缓冲区被填满，那么查找缓冲区元素中第k大的元素
*/
while (true) {
if (start + count == twoKBuffer.length) {
findElementInBuffer(0, twoKBuffer.length - 1, elementPos);
count = 0;
start = elementPos + 1;
}

twoKBuffer[start + count ] = array[n];
count++;
n++;
}
}catch (IndexOutOfBoundsException e) {
findElementInBuffer(0, start + count - 1, elementPos);
}
}

public int getKthElement() {
return twoKBuffer[elementPos];
}
}```

```public class Searching {
public static void main(String[] args) {
int n = 30;
//构造一个含指定个元素的数组
int[] arr = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) {
arr[i] = rand.nextInt(100);
}

int k = 8;
SearchKthElement sk = new SearchKthElement(arr, k);
System.out.println("The " + k + "th element in array from algorithm is :" + sk.getKthElement());

Arrays.sort(arr);
System.out.println("The " + k + "th element in array after sorting is : " + arr[k]);
}
}```

0 条评论

• 查找算法：在双重排序的数组中进行快速查找

假设A是一个n\*n的二维数组。它的行和列都按照升序排列，给定一个数值x，设计一个有效算法，能快速在数组A中查找x是否存在。同时考虑一个算法效率的下界，也就是无...

• jquery教程之查找筛选函数

三、children 取得一个包含匹配的元素集合中每一个元素的所有子元素的元素集合。

• Pseudo elements伪元素与Pseudo classes伪类

::after用于描述处于css渲染层的一个伪元素，相当于选中元素的最后一个子元素，但这个元素与DOM节点无关，位于选择的元素之后，伪元素的内容用content...

• 使用jQuery筛选排除元素以修改指定标签的属性

1、eq()　　  筛选指定索引号的元素 2、first()　　筛选出第一个匹配的元素 3、last()　　 筛选出最后一个匹配的元素 4、hasClas...

• 我不知道你知不知道我知道的伪元素小技巧

伪元素能做什么？我们要他有何用？它能为我们解决什么问题？和其他的方法相比她有什么有点？我们为什么要使用它？

• 如何使用python进行web抓取？

本文摘要自Web Scraping with Python – 2015 书籍下载地址：https：//bitbucket.org/xurongzhong/py...

• JavaWeb（八）JQuery

jQuery 市场用得比较多两个框架： jQuery 比较适合做一些互联网 的应用（12306.com,蘑菇街，美丽说，聚美） extjs 比较适合做后台管理系...