时间戳

首页 > 解决方案 > 数据结构的建议

algorithm - 数据结构的建议

问题描述

关于这个问题：

给定一个 2^n −10n ≤ A[i] ≤ 2^n 范围内的 n 个整数的未排序数组 A。建议一种数据结构，允许在 O(1) 步内回答 a 到 b 范围内的键数（注意 a、b 不一定是整数）。数据结构的构建应该花费最多 O(n) 步。

  1. 用几句话描述数据结构。
  2. 编写用于构造数据结构的伪代码。
  3. 为 numberKeys(NewDataStructure,a,b) 编写伪代码。
  4. 简述（2）和（3）的时间和空间复杂度。

有人可以解释一下是什么the number of keys in the range a to b意思吗？

感谢你的帮助！

谢谢！

标签： algorithmdata-structurestime-complexitypseudocode

解决方案

比方说n=1000

然后你在区间内有一个条目数组1000（=键，整数值，数字，...） [2^1000-10000;2^1000]。

一个问题可能是：
区间中有多少个数组条目[2^1000-9321.7;2^1000-123.2]？

推荐阅读