henryadam
BAN USERMy answer is almost the same with yours, but with slight difference.
That is, you initialize a list of "K" pairs of (A[i], B[0]) for "i = 0, 1, ..., K- 1", thus form a min heap naturally.
But I insert (A[i], B[0]) to the heap only when (A[i-1], B[0]) is extracted from the heap.See my code.
Here's the code. Most of the code is a min_heap implementation.
#include <iostream>
using namespace std;
typedef struct {
int i;
int j;
int sum;
} HeapElem;
void Swap(HeapElem* a, HeapElem* b) {
HeapElem t = *a;
*a = *b;
*b = t;
}
class MinHeap {
public:
MinHeap(int capacity): capacity__(capacity), heap_size__(0) {
heap_array__ = new HeapElem[capacity];
};
~MinHeap() {
delete[] heap_array__;
};
bool Insert(HeapElem e);
bool ExtractMin(HeapElem* e);
void PrintHeap();
private:
int LeftChild(int id) { return 2*id + 1; }
int RightChild(int id) { return 2*id + 2; }
int Parent(int id) {
if ( id == 0 ) return -1;
else return (id-1) / 2;
}
HeapElem* heap_array__;
int capacity__;
int heap_size__;
};
void MinHeap::PrintHeap() {
cout << "==============================" << endl;
cout << "heap_size:" << heap_size__ << endl;
for (int m = 0; m < heap_size__; ++m) {
cout << "elem[" << m <<"]={" << heap_array__[m].i << "," << heap_array__[m].j << "," << heap_array__[m].sum << "}" << endl;
}
cout << "==============================" << endl;
}
bool MinHeap::Insert(HeapElem e) {
if (heap_size__ == capacity__)
return false;
// cout << "Insert elem:{" << e.i << "," << e.j << "," << e.sum << "}" << endl;
heap_array__[heap_size__++] = e;
int p = heap_size__-1;
while (p != 0 && heap_array__[Parent(p)].sum > heap_array__[p].sum) {
int q = Parent(p);
Swap(&(heap_array__[p]), &(heap_array__[q]));
p = q;
}
// PrintHeap();
return true;
}
bool MinHeap::ExtractMin(HeapElem* e){
if (heap_size__ <= 0)
return false;
*e = heap_array__[0];
// cout << "Exact MinElem={" << e->i << "," << e->j <<"," << e->sum << "}" << endl;
heap_array__[0] = heap_array__[--heap_size__];
int p = 0;
while(p < heap_size__) {
int left = LeftChild(p);
if (left >= heap_size__)
break;
int min = left;
int right = RightChild(p);
if (right < heap_size__ && heap_array__[right].sum < heap_array__[left].sum)
min = right;
if (heap_array__[min].sum < heap_array__[p].sum) {
Swap(&(heap_array__[min]), &(heap_array__[p]));
p = min;
} else {
break;
}
}
// PrintHeap();
return true;
}
bool FindKthMin(int* a, int* b, int n, int k, int* v) {
if (k <= 0 || k > n*n) {
cerr << "k is invalid" << endl;
return false;
}
MinHeap heap(k);
HeapElem e = {0, 0, a[0]+b[0]};
heap.Insert(e);
HeapElem t1;
for(int m = 0; m < k; ++m) {
heap.ExtractMin(&t1);
cout << "a[" << t1.i << "]+b[" << t1.j << "]=" << a[t1.i] << "+"<< b[t1.j] << "=" << t1.sum << endl;
if (t1.j+1 < n) {
HeapElem t2 = {t1.i, t1.j+1, a[t1.i]+b[t1.j+1]};
heap.Insert(t2);
}
if (t1.j == 0 && t1.i+1 < n) {
HeapElem t3 = {t1.i+1, t1.j, a[t1.i+1]+b[t1.j]};
heap.Insert(t3);
}
}
*v = t1.sum;
cout << k << "th min value is " << *v <<endl;
return true;
}
int main () {
int v;
int a[] = {1,2,3};
int b[] = {1,4,7};
cout << "Test 0" << endl;
FindKthMin(a, b, 3, 9, &v);
int a1[] = { 1, 50, 100, 1000, 6000, 6002, 6004, 6006, 6008, 6010 };
int b1[] = {100, 200, 300, 2000, 3000, 4000, 5000, 6000, 7000, 8000 };
cout << "Test 1" << endl;
FindKthMin(a1, b1, 10, 100, &v);
int a2[] = { 1, 6, 7, 9, 10, 14 };
int b2[] = { 2, 3, 5, 8, 11, 16 };
cout << "Test 2" << endl;
FindKthMin(a2, b2, 6, 36, &v);
int a3[] = { 1, 30, 35 };
int b3[] = { 5, 6, 50 };
cout << "Test 3" << endl;
FindKthMin(a3, b3, 3, 9, &v);
int a4[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10, 11};
int b4[] = { 1, 20, 30, 40, 50, 60, 70, 80, 90,100};
cout << "Test 4" << endl;
FindKthMin(a4, b4, 10, 100, &v);
int a5[] = {3,4,5,6,13,19};
int b5[] = {1,2,5,9,10,11};
cout << "Test 5" << endl;
FindKthMin(a5, b5, 6, 36, &v);
int a6[] = {0, 1, 3, 5};
int b6[] = {1, 2, 4, 7};
cout << "Test 6" << endl;
FindKthMin(a6, b6, 4, 16, &v);
return 0;
}
B.T.W. I just want to clarify the question: do we need k minimum numbers or just the kth number? If only need the kth, we can achieve O(n^2) time complexity by taking "median of medians" algorithm. If we need k mininum numbers, the lower bound of time complexity is O(klgk).
- henryadam December 19, 2013@Alexy.
1. when k is up to n^2, actually you need to sort all these n^2 numbers. Since no appropriate linear sorting algorithm can be applied here, the lower bound of a comparison sorting algorithm' time complexity is O(n^2lgn^2)=O(n^2lgn). Theorectically, you can't do it better.
2. Although k is a variable no greater than n^2, O(n^2lgn) is only the upper bound for O(klgk). So O(klgk) is more accurate than O(n^2lgn).
#include <vector>
#include <iostream>
using namespace std;
int FindCombination(int amount, const vector<int>& domination, int max_dom_index, vector<int>* combination) {
if (amount == 0) {
int comb_size = combination->size();
if (comb_size == 0) // if original amount is 0, the combination count may be zero or infinite big number, which depends on your definition.
return 0;
// find a combination, output the combination.
for (int i = 0; i < comb_size-1; ++i) {
cout << (*combination)[i] << ",";
}
cout << (*combination)[comb_size-1] << endl;
return 1;
}
int ret = 0;
// backtracking by trying domination in descending order, thus eliminates duplications.
for (int i = max_dom_index; i >= 0; --i) {
if (amount >= domination[i]) {
combination->push_back(domination[i]);
ret += FindCombination(amount-domination[i], domination, i, combination);
combination->pop_back();
}
}
return ret;
}
int FindAllCombinations(int amount, const vector<int>& domination) {
if (domination.size() == 0)
return 0;
vector<int> combination;
return FindCombination(amount, domination, static_cast<int>(domination.size())-1, &combination);
}
int main (){
vector<int> dom; // assuming dominations have already been sorted.
dom.push_back(1);
dom.push_back(2);
dom.push_back(3);
int num = FindAllCombinations(7, dom);
cout << "====================================" << endl;
cout << "There are " << num << " combinations." << endl;
return 0;
}
A method that doesn't build a tree, but uses a queue, a children counter array, a subtree weight array instead.
1. O(n) time to determine leaf nodes, put them in a queue. (initially scan the node array from left to right, and use an array to store the number of its direct children, leaf nodes are those that have no direct children). Initialize each node's subtree weight with its own weight.
2. O(n) time to calculate the weights in a bottom-up way. You add each node's weight to its parent's subtree weight, decrease children counter of the parent node(enqueue the parent node if childern counter has dropped to zero), and then dequeue current node.
3. Output each node's weight.
It's a calculator and need compling technique. Use yacc to generate the lexical and grammar parsers. 'Parameters' are variables(look it up in a global symbol table), and reserve operators and write regular expressions for constants.
- henryadam January 07, 2014