hiho一下第205周《Building Heap》题目分析

1
0

《Building Heap》题目分析

这道题是一道比较简单的递归题目。大家一定都做过这样一道经典的题目:“已知一棵二叉树的中序和后序遍历,求先序遍历。”

这道题也是类似,堆的性质可以让我们确定最小的元素一定是根,比如在样例中1一定是根。

然后根据中序遍历的顺序,1左边的一定是左子树部分,1右边的一定是右子树的部分。

左右子树都可以递归求解。

参考代码:

void work(vector<int> &a, int l, int r) {
        int k = l;
        for (int i = l + 1; i <= r; i++) if (a[i] < a[k]) k = i;
        cout << a[k] << ' ';
        if (l < k) work(a, l, k - 1);
        if (r > k) work(a, k + 1, r);
}

int main() {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        work(a, 0, n - 1);

        return 0;
}

2 answer(s)

1

还以为是RMQ问题

  • RMQ可以优化找最小那一步,优化后最坏情况整个算法也是O(NlogN)的?上面的做法最坏情况下应该是O(N^2)的。

  • 添加评论
  • reply
0

include

using namespace std; class MyMatrix { public: MyMatrix(void); MyMatrix(size_t row,size_t col); MyMatrix(const MyMatrix& rhs); ~MyMatrix(void);

    MyMatrix& operator=(const MyMatrix& rhs);

    size_t Rows()const {return _row;};
    size_t Cols()const {return _col;};
    double& operator()(size_t r,size_t c);
    const double& operator()(size_t r,size_t c)const;

private:
    size_t _row,_col;
    double * _pmat;

};

MyMatrix::MyMatrix(void) :_row(0),_col(0),_pmat(new double[0]) {}

MyMatrix::MyMatrix(size_t row,size_t col):_row(row),_col(col),_pmat(new double[row * col]){ size_t elems = _row * _col; for(size_t i=0;i

MyMatrix::MyMatrix(const MyMatrix& rhs):_row(rhs._row),_col(rhs._col),_pmat(new double[rhs._row * rhs._col]){ size_t elems = _row * _col; for(size_t i=0;i

MyMatrix::~MyMatrix(void){ delete [] _pmat; }

MyMatrix& MyMatrix::operator=(const MyMatrix& rhs){ if(this != &rhs){ _row = rhs._row; _col = rhs._col;

    delete [] _pmat;

    size_t elems = _row *_col;
    _pmat = new double [elems];
    for(size_t i=0;i<elems;i++)
      _pmat[i] = rhs._pmat[i];
}
return *this;

}

double& MyMatrix::operator()(size_t r,size_t c){ if(r>=_row || c>=_col) throw "Error Row or Columns."; return _pmat[r*_col+c]; }

const double& MyMatrix::operator()(size_t r,size_t c)const{ if(r>=_row || c>=_col) throw "Error Row or Columns."; return _pmat[r*_col+c]; }

ostream& operator<<(ostream& os,const MyMatrix& mat){ os<

int main() { MyMatrix mat1(3,4); cout<

write answer 切换为英文 切换为中文


转发分享