返回首页
当前位置: 主页 > 网络编程 > Jsp实例教程 >

java求第K个数的问题

时间:2017-07-14 21:33来源:知行网www.zhixing123.cn 编辑:麦田守望者

一道经典的题目。给一堆数,如果从小到大排好,求第k个是多少。假设排列的下标从1开始,而非0开始。

这个问题如此之简单而熟悉,可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少,而且还可以不断演进,成为不同复杂程度的问题。

java求第K个数的问题
java求第K个数的问题
 

看到这个问题,脑海里的第一反应是一左一右红蓝两条分支——堆排序或者快排。Java中快排用Arrays.sort就可以了,如果是堆排序需要用到PriorityQueue。 用Arrays.sort写起来最简单(这里的参数校验都省掉了):
public int getKth(int[] nums, int k) {
int[] numsCopy = new int[nums.length];
System.arraycopy(nums, 0, numsCopy, 0, nums.length);

Arrays.sort(numsCopy);
return numsCopy[k - 1];
}

我拷贝了一下数组,以免对原数组做修改。 当然用PriorityQueue写起来不麻烦:
public int getKth(int[] nums, int k) {
Queue<Integer> heap = new PriorityQueue<>(k);
for (int i=0; i<nums.length; i++) {
heap.add(nums[i]);
}

int result = 0;
for (int i=0; i<k; i++)
result = heap.poll();

return result;
}

第一个相关问题来了,Arrays.sort是怎么实现的,复杂度到底是多少?

我们可以简单地认为Arrays.sort是n*log(n)的复杂度。事实上Java的实现用的不是普通的快排,而是DualPivotQuicksort,一个优化了的快速排序算法。一般的快排都是使用一个pivot,每个周期把比它小的元素扔左边,比它大的扔右边。但是DualPivotQuicksort使用了两个pivot,这样原来这堆数就分要分成三份了。在当今多数的计算机条件下,CPU计算速度原来越快,而原本被忽略的内存地址访问速度却很难有一样幅度的提高,因而显得越来越举足轻重。因此我们不能只考虑排序过程中单纯的“大小比较”次数,还需要考虑实际“地址访问”(即num[i])的开销。因为CPU的缓存等原因,在不同情形下,实际对地址访问的次数比算法理论上要少。在有意义的实际应用中,DualPivotQuicksort因为能够在多数情况下减少地址访问次数而最终比原始的快速排序更快。

第二个引申问题来了,只从算法的角度考虑,是否还有优化余地呢?

如果我只需要找到第k个,而不关心从1到k-1之间元素的顺序,也不关心从k+1到最大元素之间的顺序,那能不能通过减少这部分的多余比较,来减少一点运算时间开销呢? 其实是可以的。和上面一样,根据堆排序和快排两种思路来梳理优化方法。 先考虑堆排序。我可以修改原来的最小堆实现,由最小堆改为固定堆大小的最大堆。每次放入元素以后检查堆的大小,确保保持在k。
public int getKth(int[] nums, int k) {
Queue<Integer> heap = new PriorityQueue<>(k);
for (int i=0; i<nums.length; i++) {
heap.add(nums[i]);
if (i > k - 1)
heap.poll();
}

return heap.poll();
}

注意我初始化的时候初始化了一个大小为k的堆,而实际上我维护着的大小是k-1,这其中有一个留了一个大小为1的缓冲,是因为我都是先放进元素,再poll来调整堆的大小。因此引入这个缓冲以避免不必要的堆大小grow。 再考虑快排优化的思路,每个周期内都把比pivot小的往左边扔,比pivot大的往右边扔,而这样操作一次以后,我可以知道pivot在最后序列中的位置。如果正好是k,那皆大欢喜;如果比k大,说明要找的k在这个pivot的左边,那就再k左边继续进行这样的运算;如果比k小,那就再k右边继续这样的运算。简单来说就是包含两步:
1.search:找pivot的位置,然后根据和k的比较进一步递归pivot的左边或者是右边的子数组;
2.partition:把小的数扔pivot左边和把大的数扔pivot右边的过程。

细化来说,上述第二步这个和pivot比较并且往左或者往右扔数的逻辑是:
◾先把当前最左边的那个数选举出来作为pivot(选pivot的办法有很多,这只是最简单的一个办法),这里的pivot变量实际存储的是它的位置(下标),而其值用变量x存储;
◾然后指针cur往右走,如果发现有比pivot更小的元素,和pivot交换一下,这样操作直到最后;
◾再把最左边那个数和pivot最终应该呆的位置上的数交换一下,就使得pivot左边的数都小于pivot上的数,pivot右边的数都大于pivot上的数了。
public int getKth(int[] nums, int k) {
int[] numsCopy = new int[nums.length];
System.arraycopy(nums, 0, numsCopy, 0, nums.length);

return search(numsCopy, k - 1, 0, nums.length - 1);
}

private int search(int[] nums, int k, int left, int right) {
if (left >= right)
return nums[left];

int idx = partition(nums, left, right);
if (idx == k)
return nums[idx];
if (idx < k)
return search(nums, k, idx + 1, right);
else
return search(nums, k, left, idx - 1);
}

private int partition(int[] nums, int left, int right) {
int x = nums[left];
int pivot = left;
int cur = left + 1;
while (cur <= right) {
if (nums[cur] < x) {
pivot++;
swap(nums, pivot, cur);
}

cur++;
}

swap(nums, left, pivot);

return pivot;

}

private void swap(int[] nums, int left, int right) {
if (left == right)
return;

nums[left] ^= nums[right];
nums[right] ^= nums[left];
nums[left] ^= nums[right];
}

下面再回到最原始的解法,看堆这个分支。如果这堆数很多,但是k很小,那使用堆为了取第k个数,却需要维护一个巨大的堆,多少显得浪费。于是引出了下面这个问题:

顶一下
(0)
0%
踩一下
(0)
0%
标签(Tag):Java
------分隔线----------------------------
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:点击我更换图片
猜你感兴趣