KingsamChen的废墟堆

难得为课后习题做一次笔记，大致原因在于，某些习题虽然简单，但是却非常有意思，值得思考。

Q1：若有一个包含n个随机排列的元素的表，求出表中所有出现两次以上的元素

很显然，直接的暴力搜索不仅效率低，还稍加有点烦（要处理重复添加的问题）。

一个比较容易想到的算法是对每个元素进行统计，但是这要求高效率的搜索，一般需要依赖于Search Tree或者Hash Table之类的数据结构，实现起来稍加繁琐。

简单而又有效地方法是：先对数据进行排序，这需要O(nlogn)的渐进时间。而有序在很多情况下，是一个非常重要的推导线索。在这个题目中，直接表现为：重复的元素都是作为一块出现的。

这给了我们一个不错的思路：线性扫描元素，并统计相同元素出现的次数。当发生元素切换时，判断元素重复的次数。

如此，我们只需要额外的Θ(n)的渐进时间即可完成题目要求。虽然事先需要O(nlogn)的排序时间，但是很多情况下，输入数据可能就是有序的，这种情况下，Duplicate算法可以很优雅并且高效的解决问题。

// be sure that elements in src are sorted
void Duplicate(const vector<int>& src, vector<int>& dup)
{
	int count = 1;
	int val = src[0];
	for (unsigned int i = 1; i < src.size(); ++i)
	{
		if (val == src[i])
		{
			++count;
		}
		else
		{
			if (count > 2)
			{
				dup.push_back(val);
			}

			count = 1;
			val = src[i];
		}
	}
}

Q2：给出一个算法，求出非降序整数序列中所有的众数

所谓众数(mode)，指的是在序列中出现次数最多的那个数。

看到这个定义，再联系上面的题目，是不是觉得马上就要出结果了呢？

首先元素的有序性免去了排序的操作，其次，我们只要遵循算法1的思路，分别记录迄今最大出现次数maxCount和当前元素出现次数count，接着在元素切换时作相应的处理即可。
Read the rest of this entry »

自从算法课申请免听后，好长时间没去上课了，连老师布置什么作业都不知道…还是前几天才知道周六要交一份huffman-code上机报告。恰好最近又打算山寨下Davelv曾经写过的基于huffman-code的compression，于是周五抽了时间写了一个编码生成的demo。

huffman-code是一种经典的基于贪心策略的信息压缩编码，又称前缀编码(prefix-code)。huffman算法首先扫描文件，统计出各字符的频数，并以此为权(weight)，为每一个字符创建一个树根节点，从而形成一个森林。接着每次从森林中选取权最小的两棵树，合并。直至只剩下一颗树，即huffman tree。

huffman tree保证出现频率最高的字符所使用的编码最短。

为了减少工作量，用了C++ STL的几个容器，e.g. priority_queue，pair，vector和string。并且掠过了字符频数统计，仅实现了构建huffman tree和生成编码的接口

struct Node
{
	char c;
	unsigned int weight;
	Node* left;
	Node* right;
};
Node* ConstructHuffmanTree(const Node leaves[], int count);
void GenerateHuffmanCode(const Node* root, vector<pair<char, string> >& code, char* codeBuff, int depth);
void DestroyHuffmanTree(Node* root);
#define pop_que(x) x.top();x.pop()

int _tmain(int argc, _TCHAR* argv[])
{
	using namespace std;

	Node t[] = {{'a', 10}, {'b', 9}, {'c', 8}, {'d', 7}, {'e', 6}, {'f', 5},
				{'g', 4}, {'h', 3}};
	vector<pair<char, string> > dictCode;
	const int CODE_BUFF_SIZE = 20;
	char buf[CODE_BUFF_SIZE];

	Node* root = ConstructHuffmanTree(t, _countof(t));
	GenerateHuffmanCode(root, dictCode, buf, 0);
	DestroyHuffmanTree(root);

	for (auto iter = dictCode.cbegin(); iter != dictCode.cend(); ++iter)
	{
		cout<<iter->first<<" : "<<iter->second<<endl;
	}

	_getch();
	return 0;
}

// functor
struct CmpNode
{
	bool operator() (const Node* ele1, const Node* ele2)
	{
		return ele1->weight > ele2->weight;
	}
};

Node* ConstructHuffmanTree(const Node leaves[], int count)
{
	using namespace std;

	// copy the root of each character into the priority queue
	// in the order of weight
	priority_queue<Node*, vector<Node*>, CmpNode> prioRoot;
	for (int i = 0; i < count; ++i)
	{
		Node* tmpLeaf = new Node;
		*tmpLeaf = leaves[i];
		prioRoot.push(tmpLeaf);
	}

	// construct huffman tree
	while (prioRoot.size() >= 2)
	{
		Node* child1 = pop_que(prioRoot);
		Node* child2 = pop_que(prioRoot);
		Node* newRoot = new Node;
		assert(newRoot != NULL);

		newRoot->weight = child1->weight + child2->weight;
		newRoot->c = 0;
		newRoot->left = child1;
		newRoot->right = child2;

		prioRoot.push(newRoot);
	}

	return prioRoot.top();
}

void DestroyHuffmanTree(Node* root)
{
	if (!root)
	{
		return;
	}

	Node* left = root->left;
	Node* right = root->right;
	delete root;

	DestroyHuffmanTree(left);
	DestroyHuffmanTree(right);
}

void GenerateHuffmanCode(const Node* root, vector<pair<char, string> >& code,
						char* codeBuff, int depth)
{
	// leaf node
	if (!root->left && !root->right)
	{
		codeBuff[depth] = '\0';
		code.push_back(make_pair(root->c, string(codeBuff)));
		return;
	}

	codeBuff[depth] = '0';
	GenerateHuffmanCode(root->left, code, codeBuff, depth + 1);
	codeBuff[depth] = '1';
	GenerateHuffmanCode(root->right, code, codeBuff, depth + 1);
}

下一步的计划是，打算过段时间，从头完整实现下数据压缩，估计会在每一个阶段，写一篇Post扯下进度~

这题原来是算法课的作业，不算难，但是却可以作为算法优化的一个不错的例子。

题目描述：有两个大小均为n的有序数组A和B，求由两个数组元素组成的有序数列的中位数

思路1：由于题目的本质是求两个数组合并后的有序数组的中位数，很容易想到的是利用MergeSort的Merge过程，将两个数组合并成一个，再求出中位数即可。

算法的时间复杂制度是Θ(n)，缺点是需要额外2n的空间。

PS：由于序列是偶数，所以中位数一定是中间两个数的均值，故范围绘制应该为浮点类型

double FindMedian1(int* s1, int* s2, int n)
{
	int* tempAry = new int[2*n];
	int* p = tempAry;
	int l = 0, r = 0;

	while (l < n && r < n)
	{
		*p++ = s1[l] < s2[r] ? s1[l++] : s2[r++];
	}

	while (l < n)
	{
		*p++ = s1[l++];
	}

	while (r < n)
	{
		*p++ = s2[r++];
	}

	double median = (static_cast<double>(tempAry[n-1]) + tempAry[n]) / 2;
	delete [] tempAry;
	return median;
}

思路2：如果说思路I的线性时间复杂度尚可接受，那么其正比于输入规模的空间要求就有点让人不爽。

事实上，完全没有必要使用这个额外的空间。因为我们的目标不是合并两个有序数组，而是找到两个数组合并后的中间两个数。

所以我们只需要借助Merge，在其中增加索引计数即可以解决问题。
Read the rest of this entry »