此功能的时间复杂度是多少? [英] What is the time complexity of this function?
问题描述
以下是Java中滑动窗口最大值问题的示例解决方案.
Here's a sample solution for Sliding Window Maximum problem in Java.
给定一个数组num,有一个大小为k的滑动窗口,该窗口为 从数组的最左边移到最右边.你只能 请参阅窗口中的k个数字.每次滑动窗移动 一个位置.
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
我想弄清楚这个函数的时间和空间复杂度.我想这就是答案:
I want to get the time and space complexity of this function. Here's what I think would be the answer:
时间:O((n-k)(k * logk))
== O(nklogk)
空格(辅助):O(n)
用于返回int[]
,O(k)
用于pq
.总计O(n)
.
Space (auxiliary): O(n)
for return int[]
and O(k)
for pq
. Total of O(n)
.
这正确吗?
private static int[] maxSlidingWindow(int[] a, int k) {
if(a == null || a.length == 0) return new int[] {};
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
// max heap
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
int[] result = new int[a.length - k + 1];
int count = 0;
// time: n - k times
for (int i = 0; i < a.length - k + 1; i++) {
for (int j = i; j < i + k; j++) {
// time k*logk (the part I'm not sure about)
pq.offer(a[j]);
}
// logk
result[count] = pq.poll();
count = count + 1;
pq.clear();
}
return result;
}
推荐答案
除了--p
for (int j = i; j < i + k; j++) {
// time k*logk (the part I'm not sure about)
pq.offer(a[j]);
}
这里的执行总数为log1 + log2 + log3 + log4 + ... + logk
.这个系列的总和-
Here total number of executions is log1 + log2 + log3 + log4 + ... + logk
. The summation of this series -
log1 + log2 + log3 + log4 + ... + logk = log(k!)
第二个想法是,使用双端队列属性(O(n)
),您可以比线性算术时间解决方案做得更好.这是我的解决方案-
And second thought is, you can do it better than your linearithmic time solution using double-ended queue property which will be O(n)
. Here is my solution -
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
int indx = 0;
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// remove numbers out of range k
while (!q.isEmpty() && q.peek() < i - k + 1) {
q.poll();
}
// remove smaller numbers in k range as they are useless
while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
q.pollLast();
}
q.offer(i);
if (i >= k - 1) {
result[indx++] = nums[q.peek()];
}
}
return result;
}
HTH.
这篇关于此功能的时间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!