Pei-Jung Chen
BAN USERstd::reverse(A.begin(), A.end()); // take O(n) time
std::reverse(A.begin(), A.begin() + k); // take O(k) time
std::reverse(A.begin() + k, A.end()); // take O(n-k) time
Thus, the total time complexity is O(n) time.
- Pei-Jung Chen November 10, 2015There is no problem with the second lightest and second heaviest.
If second lightest + second heaviest > 150, then we assign a boat for only shipping second heaviest, and leave second lightest to next iteration.
There is an example: (l=light, h=heavy)
50 75 75 75 80 90 100 110 counter carry
l h 1 110
l h 2 50 + 100
l h 3 90
l h 4 80
l h 5 75+75
lh 6 75
Idea:
Use a modified Dijkstra's algorithm, and get O(klgk) algorithm.
Use the existed Selection algorithm, and get O(n) algorithm. [1]
Estimate and choose one algorithm, induce an O(min(klgk,n)) algorithm.
SelectKth(MaxHeap h, k)
n = h.size;
if ( klgk < n )
return DijkstraKth(h,k)
return SelectKthByDC(h,k)
A sample for the modified Dijkstra's algorithm.
Sample: n = 7, k = 3
[0]100 3 largest priority queue
[1]95 [2] 80 100 95 90 85 80
[3]90 [4]85 [5]75 [6]70
Sample code for the modified Dijkstra's algorithm
// 1. Memorize the index, so that we can know its child.
// 2. Use a pointer can avoid to spend additional space to memorize index.
// However, the space complexity remains O(k).
class HeapNode<Type> : IComparable where Type : IComparable
{ int i ; // index
Type v; // value
int CompareTo( HeapNode<Type> y){ return y.v - v; }
}
Type DijkstraKth(Heap<Type> h,int k) where Type: IComparable
{
if ( k > h.size )
throw Exception(“k must <= h.size”);
if ( k <= 0 )
throw Exception(“k must greater then 0);
PriorityQueue queue = new PriorityQueue();
queue.Add(h[0]); // Add the root node
while ( k>1) // k=1, return root
{ HeapNode<Type> x = queue.ExtractMax();
queue.Add(h[x.i*2 + 1]); // left node
queue.Add(h[x.i*2 + 2]); // right node
k --;
}
return queue.max().v;
}
Time Complextity:
Use a Fibonacci heap as the priority queue
2k times Add(), k times ExtractMax() => O(k) * O(lgk) = O(klgk) time
Space Complexity:
2k times Add() => O(k) space
Lower Bound:
I think it is impossible to get kth in O(lgn) worst case time.
The Lower Bound of the worst case time for large k is O(n).
The provement is by contradiction:
Assume the worst case time is lower then O(n)
let k = n, means to find the smallest.
The smallest must on the leaves.
The leaves for a balenced tree is O(n).
The elements in leaves are non-orginized.
The lower bound to find smallest element need n - 1 comparisons, that is, O(n) worst time.[2]
Contradict to the Assumption!
[1] Cormen, Leiserson, Rivest and Stein, Introduction to algorithms, third edition.p220-229
[2] Cormen, Leiserson, Rivest and Stein, Introduction to algorithms, third edition.p214-215
Repmarisamsan7, Cloud Support Associate at ADP
Hi, I am Photoengraver from an CO,USA. I am a girl with a strong desire to travel the world ...
Repkennypmillerk, AT&T Customer service email at 247quickbookshelp
My name is Kenny and I am working as a trusted investor in Pittsburgh USA.I identify / set up a ...
oOZz's code is nice and elegant.
Actually it takes 3n assignments. (Swap cost 3 assignments)
I can provide an algorithm which takes about 1n assignments. (Actually, it takes n + 2 * gcd(n,k) assignments.)
And the space remains O(1).
Let me state this question in clarified version:
Input:
1. An array A of size n
2. A rotate number k. Assume k < n.
3. Direction: For simplification, assume we always rotate to left. If we need to rotate to right, just rotate to left n-k element.
Output:
Array A after circular rotate for k elements to left.
Idea:
Since I want to use only O(1) space and n assignment. So when I move element A[j] to position 0, I have to put the correct element to the hole, and so on. This procedure make a circular movement. There is an example:
let A = {0, 1, 2, 3, 4, 5, 6, 7, 8};
let k = 6;
The above action put all element which are multiples of gcd(n,k) to correct position.
And then, I repeat the above action, but start from A[1] to A[gcd(n,k)-1]. There is an example.
Here is the code in C++
- Pei-Jung Chen November 10, 2015