武汉自动seo_网页设计代码动漫_win7优化工具哪个好用_线上营销工具

题目案例

问题描述

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

---

输入格式

1. 第一行包含整数 n 和 m。
2. 第二行包含 n 个整数，表示整数数列。

---

输出格式

共一行，包含 m 个整数，表示整数数列中前 m 小的数。

---

数据范围

• 1≤m≤n≤105
• 1≤ 数列中元素≤109

---

输入样例

5 3
4 5 1 3 2

---

输出样例

1 2 3

代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int e[N], len; //e[N]用来存储完全二叉树结构，其中2x表示左孩子，2x+1表示右孩子
int n, m;
void down(int x)
{int flag = x;if (2 * x <= len && e[flag] > e[2 * x])flag = 2 * x;  //和左右孩子比较if (2 * x + 1 <= len && e[flag] > e[2 * x + 1])flag = 2 * x + 1;if (flag != x)  //如果发现指向父结点的移到孩子结点上就说明需要调换位置了{swap(e[flag], e[x]);down(flag);}
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> e[i];}len = n;for (int i = n / 2; i; i--) //因为每次都是和这个结点的左右孩子比较，只需要从倒数第二层最后一个结点开始down(i);while (m--){cout << e[1] << " ";  //每次头结点都是最小的e[1] = e[len];   //每输出一此头节点就删掉（有点像队列），并且将最后一个结点补上重新排len--;down(1);}return 0;
}

代码思路总结

通过使用 堆（Heap） 数据结构来实现从长度为 n 的整数数列中输出前 m 小的数。具体来说，代码实现了一个 小根堆（最小堆），并通过堆的性质高效地找到前 m 小的数。以下是代码思路的详细总结：

---

1. 问题背景

• 输入一个长度为 n 的整数数列。
• 需要输出数列中前 m 小的数，按从小到大的顺序输出。

---

2. 数据结构设计

• 使用数组 e[N] 来存储完全二叉树的堆结构。
  • 完全二叉树的性质：
    • 对于节点 xx，其左孩子为 2x，右孩子为 2x+1。
    • 堆的性质：父节点的值小于等于其左右孩子的值（小根堆）。
• len 表示当前堆的大小（即堆中元素的个数）。

---

3. 核心操作

(1) 向下调整（down 函数）

• 功能：维护堆的性质，确保父节点的值小于等于其左右孩子的值。

• 实现：

  • 比较当前节点 x 与其左右孩子的值。
  • 如果当前节点的值大于某个孩子的值，则交换它们的位置。
  • 递归地对交换后的子树进行向下调整。

• 代码：

  void down(int x) {int flag = x; // flag 记录最小值的下标if (2 * x <= len && e[flag] > e[2 * x]) flag = 2 * x; // 和左孩子比较if (2 * x + 1 <= len && e[flag] > e[2 * x + 1]) flag = 2 * x + 1; // 和右孩子比较if (flag != x) { // 如果最小值不是当前节点swap(e[flag], e[x]); // 交换位置down(flag); // 递归调整}
  }
  

(2) 建堆

• 功能：将数组 e[N] 调整为一个合法的小根堆。

• 实现：

  • 从倒数第二层最后一个节点开始，依次对每个节点进行向下调整。
  • 由于完全二叉树的性质，倒数第二层的节点下标为 n/2。

• 代码：

  for (int i = n / 2; i; i--) {down(i); // 从倒数第二层开始向下调整
  }
  

(3) 输出前 m 小的数

• 功能：每次输出堆顶元素（最小值），然后删除堆顶元素并重新调整堆。

• 实现：

  • 输出堆顶元素 e[1]。
  • 将堆的最后一个元素 e[len] 移动到堆顶，并减少堆的大小 len--。
  • 对新的堆顶元素进行向下调整，恢复堆的性质。

• 代码：

  while (m--) {cout << e[1] << " "; // 输出堆顶元素（最小值）e[1] = e[len]; // 将最后一个元素移动到堆顶len--; // 堆大小减 1down(1); // 向下调整堆顶元素
  }
  

---

4. 代码流程

1. 输入数据：

   • 读取 n 和 m。
   • 读取 n 个整数并存储在数组 e[N] 中。

   cin >> n >> m;
   for (int i = 1; i <= n; i++) {cin >> e[i];
   }
   

2. 建堆：

   • 从倒数第二层开始，对每个节点进行向下调整，构建小根堆。

   len = n;
   for (int i = n / 2; i; i--) {down(i);
   }
   

3. 输出前 m 小的数：

   • 每次输出堆顶元素（最小值），然后删除堆顶元素并重新调整堆。

   while (m--) {cout << e[1] << " ";e[1] = e[len];len--;down(1);
   }
   

---

5. 复杂度分析

1. 时间复杂度：
   • 建堆：O(n)。
   • 每次删除堆顶元素并调整堆：O(log⁡n)。
   • 总时间复杂度：O(n+mlog⁡n)。
     • 当 m 较小时，复杂度接近 O(n)。
     • 当 m 接近 n 时，复杂度接近 O(nlogn)。
2. 空间复杂度：
   • 使用数组 e[N] 存储堆，空间复杂度为 O(n)。

算法刷题日记