170个可带链接锚文本外链的网站论坛,wordpress免费杂志模板,福州网站建设搭建,做网站注册什么公司好题目信息
LeetoCode地址: . - 力扣#xff08;LeetCode#xff09;
题目理解
题意简单且直观#xff0c;而且是很经典的考验快速排序以及堆排序的算法题#xff0c;很考验基本功。
堆排序写法
对points数组原地建立小顶堆
并依次弹出第1个元素#xff0c;重新调整堆…题目信息
LeetoCode地址: . - 力扣LeetCode
题目理解
题意简单且直观而且是很经典的考验快速排序以及堆排序的算法题很考验基本功。
堆排序写法
对points数组原地建立小顶堆
并依次弹出第1个元素重新调整堆顶元素再弹出第1个。。。直到弹出前K个元素。
时间复杂度: O(nlogn)
额外空间复杂度:O(k)
class Solution {int[][] points;public int[][] kClosest(int[][] points, int k) {this.points points;buildMinHeap(points, points.length);int[][] res new int[k][2];int lastIndex points.length-1;for (int i 0; ik; i) {res[i] points[0];swap(0, lastIndex--);minHeapify(0, lastIndex1);}return res;}public void buildMinHeap(int[][] points, int length) {for (int i points.length/2; i0; i--) {minHeapify(i, length);}}public void minHeapify(int i, int length) {int l i*21, r i*22;int min i;int minLength points[i][0]*points[i][0] points[i][1]*points[i][1];int lMinLength l length ? points[l][0]*points[l][0] points[l][1] * points[l][1] : Integer.MAX_VALUE;int rMinLength r length ? points[r][0]*points[r][0] points[r][1] * points[r][1] : Integer.MAX_VALUE;if (lMinLength minLength) {min l;minLength lMinLength;}if (rMinLength minLength) {min r;}if (i ! min) {swap(i, min);minHeapify(min, length);}}void swap(int a, int b) {int[] tmp points[a];points[a] points[b];points[b] tmp;}
}
快速排序写法
普通的写法是直接对整个数组排序然后取前k个元素然而这不是最高效的。
由于我们仅需要前k个元素而且不关注顺序因此可以省略到k之后元素的顺序。
假如我们当前左右边界分别是l和r,在快排中间步骤中确认了j位置元素的值后如果发现k j, 则无需再关注j到r之间元素的排序结果
类似的假如k j, 那我们也无需再关注l到j之间的元素因为我们已经确认了他们必定会出现在最终结果集中。
时间复杂度:O(n), 由于我们没有进行任何多余元素的排序动作。
额外空间复杂度:O(1), 我们是在原地进行排序没有使用额外空间。 int k;int[][] points;public int[][] kClosest(int[][] points, int k) {this.k k;this.points points;quickSort(0, points.length-1); return Arrays.copyOfRange(points, 0, k);}public void quickSort(int l, int r) {if (l r) {return;}int i l-1, j r1;int[] mid points[l (r-l)/2];while (i j) {while (compare(mid, points[i]));while (compare(points[--j], mid));if (i j) {swap(i, j);}}if (j k) {quickSort(l, j);} else if (k j1) {quickSort(j1, r);}}boolean compare(int[] a, int[] b) {return (a[0]*a[0] a[1]*a[1]) (b[0]*b[0] b[1]*b[1]);}void swap(int a, int b) {int[] tmp points[a];points[a] points[b];points[b] tmp;}
