段错误是什么原因?
老哥,这题牛客光是报错段错误,不清楚什么原因。找了一个小时了都没发现什么数组越界的情况。
代码原理堆排序:
class Solution {
public:
vector<int> GetLeastNumbers_Solution( vector<int> input, int k ) {
int len = input.size();
if (len < k)
return {};
vector<int> res( input.begin(), input.begin() + k );
//构造一个大小为k的大根堆,每次踢掉最大的,遍历完所有,最后留下的就是最小的k个
for (int i = k - 1; i >= 1; i-=2) {
helper( res, ( i - 1 ) >> 1,k);
}
for (int i = k; i < len; ++i) {
if (res[0] > input[i]) {
res[0] = input[i];
helper(res,0,k);
}
}
sort( res.begin(), res.end() );
return res;
}
void helper( vector<int> &res,int parent,int k) {
int left = ( parent << 1 ) + 1;
if (left >= k)
return;
int right = left+1;
if (right >= k) {
if (res[parent] < res[left]) {
swap( res[parent], res[left] );
helper( res, left, k );
}
return;
}
if (res[left] > res[right]) {
if (res[parent] < res[left]) {
swap( res[parent], res[left] );
helper( res, left, k );
}
} else {
if (res[parent] < res[right]) {
swap( res[parent], res[right] );
helper( res, right, k );
}
}
}
};
public:
vector<int> GetLeastNumbers_Solution( vector<int> input, int k ) {
int len = input.size();
if (len < k)
return {};
vector<int> res( input.begin(), input.begin() + k );
//构造一个大小为k的大根堆,每次踢掉最大的,遍历完所有,最后留下的就是最小的k个
for (int i = k - 1; i >= 1; i-=2) {
helper( res, ( i - 1 ) >> 1,k);
}
for (int i = k; i < len; ++i) {
if (res[0] > input[i]) {
res[0] = input[i];
helper(res,0,k);
}
}
sort( res.begin(), res.end() );
return res;
}
void helper( vector<int> &res,int parent,int k) {
int left = ( parent << 1 ) + 1;
if (left >= k)
return;
int right = left+1;
if (right >= k) {
if (res[parent] < res[left]) {
swap( res[parent], res[left] );
helper( res, left, k );
}
return;
}
if (res[left] > res[right]) {
if (res[parent] < res[left]) {
swap( res[parent], res[left] );
helper( res, left, k );
}
} else {
if (res[parent] < res[right]) {
swap( res[parent], res[right] );
helper( res, right, k );
}
}
}
};
查看24道真题和解析