lintcode130. 堆化

我会带着你远行 2023-07-05 14:51 12阅读 0赞

给出一个整数数组，堆化操作就是把它变成一个最小堆数组。  
对于堆数组A，A\[0\]是堆的根，并对于每个A\[i\]，A \[i \* 2 + 1\]是A\[i\]的左儿子并且A\[i \* 2 + 2\]是A\[i\]的右儿子。

样例
    样例 1
    
    输入 : [3,2,1,4,5]
    输出 : [1,2,3,4,5]
    解释 : 返回任何一个合法的堆数组
    挑战
    O(n)的时间复杂度完成堆化
    
    说明
    什么是堆？ 什么是堆化？ 如果有很多种堆化的结果？
    
    堆是一种数据结构，它通常有三种方法：push， pop 和 top。其中，“push”添加新的元素进入堆，“pop”删除堆中最小/最大元素，“top”返回堆中最小/最大元素。
    把一个无序整数数组变成一个堆数组。如果是最小堆，每个元素A[i]，我们将得到A[i * 2 + 1] >= A[i]和A[i * 2 + 2] >= A[i]
    返回其中任何一个。

class Solution {
        
    public:
        /*
         * @param A: Given an integer array
         * @return: nothing
         */
        void heapify(vector<int> &A) {
        
            // write your code here
            int cur=A.size()-1;
            for (int i = 0; i < A.size() ; i++) {
        
                int cur=i;
                while(cur>0)
                {
        
                    int parent=(cur-1)/2;
                    if(A[parent]<=A[cur]) {
        break;}
                    else
                    {
        
                       int tmp=A[cur];
                       A[cur]=A[parent];
                       A[parent]=tmp;
                       cur=parent;
                    }
                }
            }
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关 GLM-130B

上周六在直播里看了清华大学曾奥涵同学做的报告“从GLM-130B到ChatGLM：大模型预训练与微调”，整个报告分为三个部分，本文是根据其中的第二段“大规模语言模型系列技术：以

拼搏现实的明天。/ 2023年10月14日 13:56/ 0 赞/ 65 阅读

相关 lintcode7. 二叉树的序列化和反序列化

设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。如何反序列化或序列化二叉树是没有限制的，

今天药忘吃喽~/ 2023年07月06日 13:02/ 0 赞/ 30 阅读

相关 lintcode130. 堆化

给出一个整数数组，堆化操作就是把它变成一个最小堆数组。对于堆数组A，A\[0\]是堆的根，并对于每个A\[i\]，A \[i \ 2 + 1\]是A\[i\]的左儿子并且

我会带着你远行/ 2023年07月05日 14:51/ 0 赞/ 13 阅读

相关 130小时

昨日学习内容如下： [getComputedStyle() API][getComputedStyle_ API]动态获取元素的属性 // 语法 le

痛定思痛。/ 2022年11月29日 11:44/ 0 赞/ 146 阅读

相关 web——细心(130)——Bugku

0×00 靶场链接 [http://123.206.87.240:8002/web13/][http_123.206.87.240_8002_web13] 0×

系统管理员/ 2022年11月25日 13:24/ 0 赞/ 198 阅读

相关【LintCode 简单】22. 列表扁平化

1.问题描述：给定一个列表，该列表中的每个元素要么是个列表，要么是整数。将其变成一个只包含整数的简单列表。 2.样例：样例 1: 输入

不念不忘少年蓝@/ 2022年11月25日 13:12/ 0 赞/ 39 阅读

相关 95-10-130-启动-TransactionCoordinator

本文为博主九师兄（QQ:541711153 欢迎来探讨技术）原创文章，未经允许博主不允许转载。有问题可以先私聊我，本人每天都在线，会帮助需要的人。文章目录 1.

淡淡的烟草味﹌/ 2022年10月10日 09:56/ 0 赞/ 131 阅读

相关 C语言数据结构-排序-堆化

堆化二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。以此类

桃扇骨/ 2022年10月07日 11:46/ 0 赞/ 233 阅读

相关 LeetCode130—Surrounded Regions

LeetCode130—Surrounded Regions 原题 [https://leetcode.com/problems/surrounded-region

向右看齐/ 2022年09月22日 15:47/ 0 赞/ 93 阅读

相关 leetcode 130. Surrounded Regions

Given a 2D board containing `'X'` and `'O'`, capture all regions surrounded by `'X'`. A

Bertha 。/ 2022年07月28日 00:15/ 0 赞/ 161 阅读