- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
Given an array containing N points find the K closest points to the origin (0, 0) in the 2D plane. You can assume K is much smaller than N and N is very large.
E.g:
given array: (1,0), (3,0), (2,0), K = 2
Result = (1,0), (2,0)(result should be in ascending order by distance)
代码:
import java.util.*;
class CPoint {
double x;
double y;
public CPoint(double x, double y) {
this.x = x;
this.y = y;
}
}
public class KClosest {
/**
* @param myList: a list of myList
* @param k: the number of closest myList
* @return: the k closest myList
*/
public static CPoint[] getKNearestPoints(CPoint[] myList, int k) {
if (k <= 0 || k > myList.length) return new CPoint[]{};
if (myList == null || myList.length == 0 ) return myList;
final CPoint o = new CPoint(0, 0); // origin point
// use a Max-Heap of size k for maintaining K closest points
PriorityQueue<CPoint> pq = new PriorityQueue<CPoint> (k, new Comparator<CPoint> () {
@Override
public int compare(CPoint a, CPoint b) {
return Double.compare(distance(b, o), distance(a, o));
}
});
for (CPoint p : myList) { // Line 33
// Keep adding the distance value until heap is full. // Line 34
pq.offer(p); // Line 35
// If it is full // Line 36
if (pq.size() > k) { // Line 37
// Then remove the first element having the largest distance in PQ.// Line 38
pq.poll(); // Line 39
} // Line 40
}
CPoint[] res = new CPoint[k];
// Then make a second pass to get k closest points into result.
while (!pq.isEmpty()) { // Line 44
res[--k] = pq.poll(); // Line 45
} // Line 46
return res;
}
private static double distance(CPoint a, CPoint b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
}
问题:
What is time complexity for line 35, line 39, independently and separately?
What is time complexity for line 35 - 40 (As a whole) ?
What is time complexity for line 44 - 46 (As a whole) ?
What is overall time complexity for entire method getKNearestPoints(), in best, worst and average case? What if n >> k ? and what if we don't have n >> k ?
实际上这些问题是我在技术面试中提出的几个问题,但我仍然有点困惑。感谢您的帮助。
最佳答案
看来,我想写这段代码的人一定知道这些问题的答案。
反正这里的Priority Queue是基于Max Heap实现的。
所以,复杂度如下:
第 35 行 - O(log k)
向堆中插入一个元素的时间。插入时在堆中遵循自下而上的方法。
第37行 - O(1)
, 检查堆大小的时间,一般是随堆一起维护。
第39行 - O(log k)
,移除堆头的时间,根部的heapify方法应用堆以移除堆的顶部。
第35-40行:从上面的复杂度我们可以看出,一次迭代的整体复杂度将是O(log k)
。此循环针对 n
个元素运行,因此整体复杂度将为 O(n log k)
。
第44-46行:检查堆大小的复杂度又是O(1)
,轮询是O(log k)
。所以我们正在轮询 k
次。循环的整体复杂度为 O(k log k)
。
总体复杂度将保持 O(n log k)
。
This是研究这个主题的好地方。
关于java - {Java - PriorityQueue} 这段代码的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46627634/
采用另一个优先级队列的 java API PriorityQueue 构造函数是否会破坏参数?如果是这样,它的clone()方法足以创建浅拷贝吗? 最佳答案 不,它不是破坏性的。几乎所有集合类都有复制
我正在尝试复制一个 PriorityQueue 对象。 我的目标是在不修改我原来的 PriorityQueue 的情况下更改我的 Copy 的某些对象 为了这样做,我复制了我的 PriorityQue
我正在解决leetcode的Merge K Sorted Lists problem . 使用 Python2 的 Queue 模块中的 PriorityQueue 的相同算法会为 Python3 的
当 PriorityQueue.size() > 0 在 Android 上时,当 PriorityQueue.peek() 返回 null 时,我遇到了问题。 我认为这可能是设备问题。有人有什么想法
我有一个asyncio.PriorityQueue,用作网络爬虫的URL队列,当我调用url_queue.get时,得分最低的URL首先从队列中删除()。当队列达到 maxsize 项时,默认行为是阻
完全二叉树 一棵深度为k的有n个结点的 二叉树 ,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与 满二叉树 中编号为i的结点在二叉树中的位置相同,则这棵
我很难理解 priorityqueue 如何使用 compareTo 方法对其内容进行排序。 我在上一门名为 Node.js 的类(class)。它有 4 个字段。 private char char
我目前有一种方法使用 scala.collection.mutable.PriorityQueue 按特定顺序组合元素。例如代码看起来有点像这样: def process[A : Ordering]
没有提供自定义比较器,优先级队列按升序插入元素,但是,在删除特定元素后,顺序会发生变化。 PriorityQueue pq = new PriorityQueue<>(); pq.add(10); p
这个问题已经有答案了: The built-in iterator for java's PriorityQueue does not traverse the data structure in a
已关闭。这个问题是 not reproducible or was caused by typos 。目前不接受答案。 这个问题是由拼写错误或无法再重现的问题引起的。虽然类似的问题可能是 on-top
我指的是此博客上列出的代码:https://strstr.io/Leetcode1054-Distant-Barcodes/ 我在这里复制这段代码 class Solution { publi
这个问题已经有答案了: Why does PriorityQueue.toString return the wrong element order? [duplicate] (4 个回答) 已关闭
我有一个比较器类 NComparator,它比较 2 个 Node 对象并返回 1、-1 或 0。 我初始化了一个初始容量为 100 的 PriorityQueue 和那个 NComparator。
当项目是整数与字符串时,PriorityQueue 的不同行为让我非常困惑。但在解决这个问题之前,我想了解以下行为(使用项目作为整数)。 假设我有一个包含以下数据的优先级队列(对于每个元素,第一个值是
我有使用 PriorityQueue 的程序。 poll() 没有给出队列中的所有值。 class Coffee { public static void main(String[] args
所以我正在尝试构建我的第一个 prim 算法,为此我根据其权重按优先级对边缘进行排序。 所以我认为如果我使用优先级队列会很有帮助,为此我需要让我的边缘实现 Comparable<> 接口(interf
编译器(Java 8)提示以下代码没有合适的构造函数: PriorityQueue heap = new PriorityQueue((ListNode n1, ListNode n2) -> n1.
我有一个优先级队列,我在其中添加一个节点对象,其中节点应按它们包含的值排序。由于某种原因,优先级队列不会在添加时对节点进行排序。如果有人能发现其中的问题或有任何指导,我很感激。这是一个简短的示例: P
这是我在这里发表的第一篇文章,因此请随时为我指出关于在这里提出问题的正确方向。 我的问题出在 java.util.PriorityQueue 上。 我有一个初始化的队列; myComparab
我是一名优秀的程序员,十分优秀!