xialijun0801
BAN USERsuppose the functions in stack include:
void empty();
element pop();
void push(element);
then
class queue{
stack stack1;
stack stack2;
void push_back(element)
{stack2.push(element);
}
void push_front(element)
{stack1.push(element);
}
element pop_front()
{ if (stack1.empty())
restack(stack1, stack2);
if (stack1.empty()) return null; else return stack1.pop();
}
element pop_back()
{ if (stack2.empty())
restack(stack2, tack1);
if (stack2.empty()) return null; else return stack2.pop();
}
void restack(stack stack1, stack stack2)
{while (!stack2.empty())
{element = stack2.pop();
stack1.push(element);
}
}
After each iteration, you only need to do the recursion for either the left part or the right part. T(n) = T(n/2) + n
which means the total time is n + n/2 + n/4......= 2n, which is O(n)
Random select a number from the array, used it as pivot, then the numbers smaller than this goes to the left, the numbers larger than this goes to the right. Check the location of this pivot (m), if it is larger than k, then do this recursively to the left part, if it is smaller than k, then store the left part to the answer, and do this recursively to the right part, with k=k-m;
Time is O(N)
Even I am Chinese I don't understand the Chinese expressions used in computer science, so please type in English
- xialijun0801 February 04, 2014