LintCode "Heapify"
2024-10-11 02:16:28
My first try was, using partial sort to figure out numbers layer by layer in the heap.. it only failed with TLE with the last test case. The problem is, partial sort cannot guaratee O(n) every time.
class Solution
{
void kth(vector<int> &A, int s, int e, int k) // all zero based
{
if(s >= e) return; // Partition
int i = e, j = e;
{
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(s, e); int pi = dis(gen);
int pivot = A[pi];
swap(A[pi], A[s]); while(j > s)
{
if(A[j] >= pivot)
{
swap(A[i], A[j]);
i --; j = i;
}
else
{
j --;
}
}
swap(A[i], A[s]);
} // Recursion
if(i < k)
{
kth(A, i + , e, k);
}
else if(i > k)
{
kth(A, s, i - , k);
}
}
public:
/**
* @param A: Given an integer array
* @return: void
*/
void heapify(vector<int> &A)
{
size_t n = A.size();
int s = , e = n - ;
while (s < e)
{
int cnt = e - s + ;
int h = ceil(log2(cnt));
int k = (pow(, h) - )/;
kth(A, s, e, k - );
e = k - ;
}
}
};
A smarter way is as below. Its strategy is "per-node maintanence".
class Solution {
void help(vector<int> &A, int i)
{
int n = A.size();
int li = i * + , ri = i * + ;
int left = li < n ? A[li] : INT_MAX;
int right= ri < n ? A[ri] : INT_MAX;
if(left < right && left < A[i])
{
swap(A[li], A[i]);
help(A, li);
}
else if(right < left && right < A[i])
{
swap(A[ri], A[i]);
help(A, ri);
}
}
public:
/**
* @param A: Given an integer array
* @return: void
*/
void heapify(vector<int> &A) {
for(int i = A.size() / ; i >= ; i --)
help(A, i);
}
};
最新文章
- SELECT INTO 和 INSERT INTO SELECT 两种表复制语句
- MVC复杂模型绑定
- 操作ACCESS数据库注意事项
- iOS 5.0 后UIViewController新增：willMoveToParentViewController和didMoveToParentViewCon［转］
- iOS中UITableView的cell点击事件不触发didSelectRowAtIndexPath（汇总）
- 使用bootstrap时，选项框出现的意外效果，怎么办？
- ASP.NET Zero--15.一个例子（8）商品分类管理-权限控制
- python在cmd上导包成功，但是python charm上面就提示找不到
- 自动化测试—monkeyrunner
- jmeter-Java-MongoDB 数据库增删改查操作
- js 闭包，作用域，this 终结篇(转)
- JAVA程序设计的第一次作业
- unittest的使用二——生成基于html的测试报告
- 【leetcode-84】 柱状图中最大的矩形
- C# 随机四位数验证码
- 使用phpExcel导出excel文件
- js API
- JavaScript设计模式-18.享元模式
- 数组B - 我想我需要一艘船屋
- 海康ipc onvif抓包分析