s*****b
发帖数: 45 | 1 Moving-window maximum.
Input: A long array A[], and a window width w
Output: An array B[],B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: find a good optimal to get B[i]
I can think of two solutions
First solution:
if(A[i] = !B[i-1]) B[i] = B[i-1]
else B[i] = max{A[i],...A[i+w-1]}
Second solution(this one is from one of my friend)
Use minHeap to store w number, each time when a new number A[i] enters,
age out the oldest one, and use O(logW) time to get max value of A[i-w+1]
to A[i]
Any good ideas or better solutions? | D*****7
发帖数: 766 | 2 可以以你朋友的方案为基础再优化一下。
1) sort the cache used to store the w number
2) when a new number A[i] comes:
if (A[i] == A[i-w])
// nothing to do
else if (A[i] > A[i-w])
// 从后向前遍历cache，先是删除A[i-w]，然后不断的cache[j]=cache[j-1]，
直到将A[i]插入cache
else
// 从前向后遍历cache，先是删除A[i-w]，然后不断的cache[j]=cache[j+1]，
直到将A[i]插入cache
【在 s*****b 的大作中提到】
: Moving-window maximum.
: Input: A long array A[], and a window width w
: Output: An array B[],B[i] is the maximum value of from A[i] to A[i+w-1]
: Requirement: find a good optimal to get B[i]
: I can think of two solutions
: First solution:
: if(A[i] = !B[i-1]) B[i] = B[i-1]
: else B[i] = max{A[i],...A[i+w-1]}
: Second solution(this one is from one of my friend)
: Use minHeap to store w number, each time when a new number A[i] enters,
| i**********e
发帖数: 1145 | 3 You said use minHeap, that's fine :)
But how to age out the oldest one? You have to search for the heap right?
The key to answering this problem is remove the leftmost element as
efficient as possible.
Hint: Hash table
Deng107:
You're doing a linear search in the heap. The worst case would happen such that your cache won't help at all. So you need O(w) to remove the leftmost element in each pass.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*****b 的大作中提到】
: Moving-window maximum.
: Input: A long array A[], and a window width w
: Output: An array B[],B[i] is the maximum value of from A[i] to A[i+w-1]
: Requirement: find a good optimal to get B[i]
: I can think of two solutions
: First solution:
: if(A[i] = !B[i-1]) B[i] = B[i-1]
: else B[i] = max{A[i],...A[i+w-1]}
: Second solution(this one is from one of my friend)
: Use minHeap to store w number, each time when a new number A[i] enters,
| k*****a
发帖数: 188 | 4 Hash table can help remove the leftmost element, but how to make sure the
heap is sorted? | i**********e
发帖数: 1145 | 5 The minHeap maintain the order when an element is being inserted. The insert
operation takes O(lg N) time complexity.
>> Hash table can help remove the leftmost element ...
Could you explain how? Many people know that the minHeap is the right data structure, but how hash table helps to accomplish removing the leftmost element in O(1) time is the heart of this problem.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | k*****a
发帖数: 188 | 6 Maintain a hash table so that given the value of leftmost element, you can
know the position in minHeap | i**********e
发帖数: 1145 | 7 这明显不对啊
首先，在 minHeap 里只能 O(1) 索取排在第一位的元素。 minHeap 不是 array，不能
O(1) random access.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 k*****a 的大作中提到】
: Maintain a hash table so that given the value of leftmost element, you can
: know the position in minHeap
| i**********e
发帖数: 1145 | 8 另外，要补充一下，这题的思路有一小部分跟一道经典题 "Finding the Minimum
Window in S which Contains All Elements from T" 很相似。
做了这题之后，你会发现 hash table 可以利用得如此巧妙.
强烈推荐参考 stormrage 兄给的精简答案：
http://www.mitbbs.com/article_t/JobHunting/31731763.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | h*********3
发帖数: 111 | 9
想了半天也没想出2题的相似之处 。。。。。
觉得还是用hash+heap,hash把 index of the array 影射为一个指针，指向这个结点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW).
【在 i**********e 的大作中提到】
: 另外，要补充一下，这题的思路有一小部分跟一道经典题 "Finding the Minimum
: Window in S which Contains All Elements from T" 很相似。
: 做了这题之后，你会发现 hash table 可以利用得如此巧妙.
: 强烈推荐参考 stormrage 兄给的精简答案：
: http://www.mitbbs.com/article_t/JobHunting/31731763.html
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| i**********e
发帖数: 1145 | 10 你这方法我想了想，应该是不行的。
试想想，假设有重复的数字怎么处理呢？
[3, 5, 2], 5
hash[5] = pointer that point to node with value 5.
sliding window move to the right 1 step.
3, [5, 2, 5]
Now, you have two 5's. If you choose hash[5] to point to the first 5, which
will be deleted next, so now hash[5] points to nothing!
这问题最优解好像是 O(N)，大家再努力想想吧。
（以下的解法是利用 hash table 来数每一个数字出现的次数，不是最优解，复杂度为
O(N lg W)，W = sliding window 的长度
#include
#include
#include
#include
#include
using namespace std;
int main() {
freopen("data.txt", "r", stdin);
int n, w;
int* arr = new int[1000001];
int* outMax = new int[1000001];
priority_queue qMax;
hash_map h;
cin >> n >> w;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
outMax[0] = INT_MIN;
for (int i = 0; i < w; i++) {
qMax.push(arr[i]);
h[arr[i]]++;
if (arr[i] > outMax[0])
outMax[0] = arr[i];
}
for (int i = w; i < n; i++) {
qMax.push(arr[i]);
h[arr[i]]++;
h[arr[i-w]]--;
int topMax = qMax.top();
while (h[topMax] == 0) {
qMax.pop();
topMax = qMax.top();
}
outMax[i-w+1] = topMax;
}
for (int i = 0; i < n-w+1; i++) {
cout << outMax[i];
if (i != n-w) cout << " ";
}
cout << endl;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW).
【在 h*********3 的大作中提到】
:
: 想了半天也没想出2题的相似之处 。。。。。
: 觉得还是用hash+heap,hash把 index of the array 影射为一个指针，指向这个结点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW).
| | | b*****c
发帖数: 165 | 11 This is also the interview question of Google.
Please check the following link for perfect solution:
http://www.mitbbs.com/article_t1/JobHunting/31728173_0_1.html | H******7
发帖数: 1728 | 12 h[arr[i]]++;
这一句什么意思？
C++不是很熟。请指点一下
which
【在 i**********e 的大作中提到】
: 你这方法我想了想，应该是不行的。
: 试想想，假设有重复的数字怎么处理呢？
: [3, 5, 2], 5
: hash[5] = pointer that point to node with value 5.
: sliding window move to the right 1 step.
: 3, [5, 2, 5]
: Now, you have two 5's. If you choose hash[5] to point to the first 5, which
: will be deleted next, so now hash[5] points to nothing!
: 这问题最优解好像是 O(N)，大家再努力想想吧。
: （以下的解法是利用 hash table 来数每一个数字出现的次数，不是最优解，复杂度为
| H******7
发帖数: 1728 | 13 h[arr[i]]++;
h[arr[i-w]]--;
C++里 的HASHMAP我不熟悉。这是在做什么？谢谢 | k*****a
发帖数: 188 | 14 No hash table needed, a linked list can solve that, to map index of window
to index of minHeap, notice minHeap can be stored in an array. So for each
element, the time to maintain the linked list is O(1), the time to add/
delete in minHeap is O(1), the time to maintain a minHeap is between O(1) to
O(lg k).
Based on these, on average, it is O(n), in the worst case (removing root of
minHeap each time in case an sorted vector), it is O(n lg k)
which
【在 i**********e 的大作中提到】
: 你这方法我想了想，应该是不行的。
: 试想想，假设有重复的数字怎么处理呢？
: [3, 5, 2], 5
: hash[5] = pointer that point to node with value 5.
: sliding window move to the right 1 step.
: 3, [5, 2, 5]
: Now, you have two 5's. If you choose hash[5] to point to the first 5, which
: will be deleted next, so now hash[5] points to nothing!
: 这问题最优解好像是 O(N)，大家再努力想想吧。
: （以下的解法是利用 hash table 来数每一个数字出现的次数，不是最优解，复杂度为
| h*********3
发帖数: 111 | 15
which
我是说hash index, 不是hash value, 你的例子里面，第一个5的index是2，第2个5
的index是5，index不会重复。
【在 i**********e 的大作中提到】
: 你这方法我想了想，应该是不行的。
: 试想想，假设有重复的数字怎么处理呢？
: [3, 5, 2], 5
: hash[5] = pointer that point to node with value 5.
: sliding window move to the right 1 step.
: 3, [5, 2, 5]
: Now, you have two 5's. If you choose hash[5] to point to the first 5, which
: will be deleted next, so now hash[5] points to nothing!
: 这问题最优解好像是 O(N)，大家再努力想想吧。
: （以下的解法是利用 hash table 来数每一个数字出现的次数，不是最优解，复杂度为
| k*****a
发帖数: 188 | 16 这个跟我最开始的思路一样， 握手 . 但是不用hash table做mapping，linked
list就可以O（1）把 index of the array 影射为一个指针，hash反而复杂。
点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW).
【在 h*********3 的大作中提到】
:
: which
: 我是说hash index, 不是hash value, 你的例子里面，第一个5的index是2，第2个5
: 的index是5，index不会重复。
| i**********e
发帖数: 1145 | 17 Thanks for the link.
According to AprilFlower:
>> 永远是从尾插入的，只要O(1)的。
如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表
maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删
除一次，所以整个的复杂度是O(n)。。
I think I coded the solution and submitted here at POJ online judge:
http://poj.org/problem?id=2823
I uploaded a copy of my code here (Sorry it's a bit messy and there's part
that I copy and paste here and there :( ) The basic idea is using a doubly-linked list and maintain the linked list by only doing insert/remove operation at the two ends of the list.
http://www.ideone.com/16Xfp
However, I get Time limit exceeded... Any suggestion? Did I implement it
wrongly?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 b*****c 的大作中提到】
: This is also the interview question of Google.
: Please check the following link for perfect solution:
: http://www.mitbbs.com/article_t1/JobHunting/31728173_0_1.html
| i**********e
发帖数: 1145 | 18 这代表 hash table 里的值加一个 或者 减一。
一开始的初始值是 0.
h[0]++ --> increment h[0] by 1, now h[0] = 1
h[3]-- --> decrement h[3] by 1, now h[3] = -1
h[0]++ --> increment h[0] by 1, now h[0] = 2
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 H******7 的大作中提到】
: h[arr[i]]++;
: h[arr[i-w]]--;
: C++里 的HASHMAP我不熟悉。这是在做什么？谢谢
| i**********e
发帖数: 1145 | 19 kongbua,
>> Based on these, on average, it is O(n), in the worst case (removing root
of minHeap each time in case an sorted vector), it is O(n lg k)
I don't think this statement is correct. Your average is still O(n lg k). Based on your statement:
The time to maintain a minHeap is between O(1) to O(lg k). This does not prove that the average case is O(N).
>> 这个跟我最开始的思路一样， 握手 . 但是不用hash table做mapping，linked
list就可以O（1）把 index of the array 影射为一个指针，hash反而复杂。
Sorry I misunderstood. Could you please paste your code (or pseudocode)? I
don't quite understand how you can use linked list to map to an element's
index. (Is it the node store the data (a pointer) that points to an element?)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
to
of
【在 k*****a 的大作中提到】
: No hash table needed, a linked list can solve that, to map index of window
: to index of minHeap, notice minHeap can be stored in an array. So for each
: element, the time to maintain the linked list is O(1), the time to add/
: delete in minHeap is O(1), the time to maintain a minHeap is between O(1) to
: O(lg k).
: Based on these, on average, it is O(n), in the worst case (removing root of
: minHeap each time in case an sorted vector), it is O(n lg k)
:
: which
| P********l
发帖数: 452 | 20 O(n) algorithm:
public Integer[] getMaxInSlideWindow(Integer[] A, Integer w) {
// invalid input
if (A == null || w <= 0 || A.length - w + 1 <= 0)
return null;
Integer[] B = new Integer[A.length - w + 1];
// auxiliary queue that is sorted in descending order
List q = new LinkedList();
for (int i = 0; i < A.length; i++) {
// enqueue. Remove those smaller values
int data = A[i];
while (!q.isEmpty() && q.get(q.size() - 1) < data) {
q.remove(q.size() - 1);
}
q.add(data);
if (i < w - 1)
continue;
// dequeue. If the current number is the maximum. Also remove it
// from the queue
Integer max = q.get(0);
B[i - w + 1] = max;
if (A[i - w + 1] == max)
q.remove(0);
}
return B;
} | | | P********l
发帖数: 452 | | i**********e
发帖数: 1145 | 22 Nice solution.
My algorithm is the same as yours, although your code is much more elegant,
good job!
I submitted your code (with some modification) to here, it still gives me
Time Limit Exceeded.
Could you try to submit your code here? (You would need to output the
minimum sliding window value as well).
http://poj.org/problem?id=2823
This solution which uses the simple idea of heap + linear search in heap
passes the judge.
http://blogold.chinaunix.net/u3/105033/showart_2209043.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 P********l 的大作中提到】
: O(n) algorithm:
: public Integer[] getMaxInSlideWindow(Integer[] A, Integer w) {
: // invalid input
: if (A == null || w <= 0 || A.length - w + 1 <= 0)
: return null;
: Integer[] B = new Integer[A.length - w + 1];
: // auxiliary queue that is sorted in descending order
: List q = new LinkedList();
: for (int i = 0; i < A.length; i++) {
: // enqueue. Remove those smaller values
| i**********e
发帖数: 1145 | 23 Sorry, I've deleted some of my previous posts to avoid confusion. kongbua is right, this problem actually does not require hash table.
A single priority queue is sufficient. Instead of pushing the array's value
into the queue, push the array's index into the queue. Apply the queue's
ordering that is based on the array's value, not its index. The average
complexity of this method is k*(N-W) lg W. Is this O(N) or O(N lg W)? I
think this is O(N), since W <= N, lg W is pretty significant compared to N,
in addition W is a constant. (I am not 100% sure though)
The other method is to maintain a single linked list. This is O(N) because
there are total maximum of 2*N insert/remove operations onto the list at
most.
Which method is faster? In theory, it seemed that the second method is
faster. In real life however, I guess this is still debatable, because
depending on the constant factor, the queue method might be faster.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | P********l
发帖数: 452 | 24 The code is accepted. But note that it consumes 40M memory + 36.5s. I
don't know what funky test data they used. Somehow the robot judge does
not accept the "package", I get "run time error" 9 times.
8111807 puttyshell 2823 Accepted 40168K 36454MS Java
2357B 2011-01-23 14:34:47 | c******n
发帖数: 4965 | 25 这个方法对这个题是最优，但是heap-based solution 实际上解决了另一个更难的问题：
求moving window of width W 里面最大的K 个数。
【在 P********l 的大作中提到】
: O(n) algorithm:
: public Integer[] getMaxInSlideWindow(Integer[] A, Integer w) {
: // invalid input
: if (A == null || w <= 0 || A.length - w + 1 <= 0)
: return null;
: Integer[] B = new Integer[A.length - w + 1];
: // auxiliary queue that is sorted in descending order
: List q = new LinkedList();
: for (int i = 0; i < A.length; i++) {
: // enqueue. Remove those smaller values
| l******l
发帖数: 66 | 26 This sounds like a simple problem, O(N) time, O(1) space.
First calculate the sum of the left-most window. Then slide the window from
left to right step by step, update current sum by subtracting the one just
removed and adding the one just added. Update the current maximum sum and its start index. After one scan, copy the maximun window to the output. | d****2
发帖数: 12 | 27 shouldn't this be simpler by just using an array based stack, so that you
don't have to maintain link node and allocate new memory? A c++ version:
void MovingWindowMax(int* a, int n, int w, int* b)
{
Stack* stack = new Stack(w); //an array implementation of stack.
max capacity is w at any time.
for(int i=0; i
{
while(!stack.Empty() && stack.Peek() < a[i])
stack.Pop();
stack.Push();
if(i
continue;
b[i-w+1] = stack.Peek();
if(a[i-w+1] == b[i-w+1])
stack.Pop();
}
} | i**********e
发帖数: 1145 | 28 Try this example:
n = 3, w = 2.
a = [5 4 3]
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
.
【在 d****2 的大作中提到】
: shouldn't this be simpler by just using an array based stack, so that you
: don't have to maintain link node and allocate new memory? A c++ version:
: void MovingWindowMax(int* a, int n, int w, int* b)
: {
: Stack* stack = new Stack(w); //an array implementation of stack.
: max capacity is w at any time.
: for(int i=0; i: {
: while(!stack.Empty() && stack.Peek() < a[i])
: stack.Pop();
|
|
