首页 > 代码库 > 算法导论 第六章 思考题6-3 Young氏矩阵
算法导论 第六章 思考题6-3 Young氏矩阵
这题利用二叉堆维持堆性质的办法来维持Young氏矩阵的性质，题目提示中写得很清楚，不过确实容易转不过弯来。
a,b两问很简单。直接看c小问：
按照Young氏矩阵的性质，最小值肯定在左上角取得，问题在于取出最小值后如何保持矩阵的性质。可以参照max_heapify中的做法，先取出最小值，然后将矩阵左上角置为最大值，这样左上角处的元素必然导致Young氏矩阵的性质违背，于是考虑该元素右边的元素和该元素下边的元素，问题是该与右边元素交换还是与下边元素交换呢？可以发现，如果与T(右)和T(下)中较小的一个元素交换，可以使得另一元素所在的行或列恢复Young氏矩阵性质，这样就把待调整的矩阵的规模减小到了(m - 1) X n 或 m X (n - 1)。递归运行这个过程，直到待调整的矩阵为空，因为每次都将m或n减小1，直到它们都减小到零为止，可知时间复杂度为O(m + n)
d小问实现插入过程，还是参照二叉堆中的插入过程，把新元素插入到矩阵末尾，然后向左上角调整直到到达合适的位置。调整过程的思路其实跟c中的思路类似。这次是与新元素左边元素和上边元素比较。可以发现，如果我把新元素和T(左)、T（上）中较大的元素进行交换，可以使得另一个元素所在的行（或列）恢复Young氏矩阵性质，于是同样把待调整的矩阵规模减小到(m - 1) X n 或m X （n - 1）
e比较直接，extract_min需要线性时间O(n),共有n^2个元素，于是复杂度就是O(n^3)
f问比较难想，我折腾了好久。关键是查找位置是从矩阵的左下角开始。这位置很巧妙，如果k大于它，那它所在的列就不用找了，如果k小于它，那它所在的行就不用找了，也是逐次减小矩阵规模查找元素。
部分实现的源码如下：
#include<iostream>#include<vector>using namespace std;enum class Direction{DOWN, RIGHT, UP, LEFT, OVER};void extract_helper(vector<vector<int> > &Young, int m, int n){ Direction d = Direction::OVER; int val = Young[m][n]; if (m + 1 < Young.size() && val > Young[m + 1][n]){ d = Direction::DOWN; val = Young[m + 1][n]; } if (n + 1 < Young[0].size() && val > Young[m][n + 1]){ d = Direction::RIGHT; val = Young[m][n + 1]; } switch (d){ case Direction::DOWN: swap(Young[m][n], Young[m + 1][n]); extract_helper(Young, m + 1, n); break; case Direction::RIGHT: swap(Young[m][n], Young[m][n + 1]); extract_helper(Young, m, n + 1); break; case Direction::OVER: break; } return;}int extract_min(vector<vector<int>> &Young){ int min = Young[0][0]; Young[0][0] = INT_MAX; int m = 0; int n = 0; extract_helper(Young, m, n); return min;}void insert_helper(vector<vector<int>> &Young, int m, int n){ Direction d = Direction::OVER; int val = Young[m][n]; if (m - 1 >= 0 && val < Young[m - 1][n]){ val = Young[m - 1][n]; d = Direction::UP; } if (n - 1 >= 0 && val < Young[m][n - 1]){ val = Young[m][n - 1]; d = Direction::LEFT; } switch (d){ case Direction::UP: swap(Young[m][n], Young[m - 1][n]); insert_helper(Young, m - 1, n); break; case Direction::LEFT: swap(Young[m][n], Young[m][n - 1]); insert_helper(Young, m, n - 1); break; case Direction::OVER: break; }}void insert(vector<vector<int>> &Young, int key){ int M = Young.size(); int N = Young[0].size(); Young[M - 1][N - 1] = key; int m = M - 1; int n = N - 1; insert_helper(Young, m, n);}void Young_sort(vector<vector<int>> &Young, vector<int>& result){ while (Young[0][0] != INT_MAX){ int key = extract_min(Young); result.push_back(key); }}
算法导论 第六章 思考题6-3 Young氏矩阵