当前位置: 首页 > 面试题库 >

没有内置的动态数组吗?

蓬兴国
2023-03-14
问题内容

我刚刚开始学习go,并且正在研究数据结构。我习惯于像listin pythonstd::vectorin
这样的动态数组C++,但是在in 中看不到任何类似的东西go动态数组的优点是添加新元素的时间复杂度为O(1),用于索引的时间复杂度为O(1)。

首先我以为slice是这样,但是后来我意识到,当我使用append函数时,整个分片都将被复制,因此它是一个O(N)操作,而不是动态数组中的O(1)。

然后我遇到了list,但这是一个双链表,这意味着索引是O(N),而不是O(1)。

我是否缺少要查找的数据结构?


问题答案:

首先我以为slice是这样,但是[n]我意识到当我使用append函数时,整个分片都将被复制,因此它是一个O(N)运算,而不是动态数组中的O(1)。

这是不正确的。

根据 《 Go编程语言规范》append检查支持切片的阵列的容量,并且仅在支持阵列中没有足够空间的情况下分配新内存(复制切片)。[
链接
]我没有在规范中看到任何指定它应该分配多少内存的内容,但是根据您链接到的博客文章,新的内存块将是当前切片大小的1.5倍。即是,一个再分配后/复制插入装置,下一个
Ñ / 2的插入将 不会 需要重新分配/复制。总体效果是摊销O(1)时间。这与您在其他语言(listPython,std::vectorC
++)中提到的示例所使用的方法相同。

因此,切片正是您所需要的。



 类似资料:
  • 我有一个数据帧字段,它是一个<code>Seq[Seq[String]. 我的用例是字符串,但显然,这可能是通用的。您可以在数据帧转换链中使用此函数,如: 是否有一个Spark内置函数可以做同样的事情?我找不到一个。

  • array.h #include<stdio.h> #include<stdlib.h> struct data { int *p;//指针保存数组的起始点 int length;//保存数组的长度 int stat;//0代表无序,1代表有序从小到大,2有序从大到小 int reallength;//实际分配的内存长度 };

  • 我有一个页面,需要动态创建一个iframe并将其粘贴到页面上的div中。我创建iframe的方式如下: 根据某些条件,我需要:A)将iframe src设置为其他页面,或者B)动态地向iframe添加一些HTML。 我有选项A的罚款,但选项B抛出了安全错误: 在尝试设置HTML之前,是否需要在动态iframe上设置?我怎么会那么做呢?有没有更简单的方法将动态内容附加到动态iframe中? 提前道谢

  • 我们想为房间数据库构建一个过滤器,过滤器选项由用户选择。 i、 e.我们有一个带有字段(id、名称、日期、类型)的实体。用户可以按日期和/或名称过滤列表,其中包含文本和/或类型等于某个值 有办法在房间里做吗?

  • 问题内容: 我正在学习Java编程课程,并且需要有关动态数组的帮助。我环顾四周,找不到解决方法,这只是我的简单程度。我上课不远,只是学习了基础知识,所以我不太了解,但是我需要知道如何制作动态数组。 这是我们获得的两个示例程序: 2号 第二个应该继承第一个,并允许您在键入后创建更多数组。但是当我使用它们时,它说我有一个错误,并且说只有在明确要求注释处理的情况下,类名称才被接受。 问题答案: 将此用于

  • 主要内容:ArrayList 类中的属性,ArrayList 类中的方法在 C# 中,动态数组(ArrayList)代表了可被单独索引的对象的有序集合。动态数组基本上可以代替数组,唯一与数组不同的是,动态数组可以使用索引在指定的位置添加和移除指定的项目,动态数组会自动重新调整自身的大小。另外,动态数组允许在列表中进行动态内存分配、增加、搜索、排序等操作。 ArrayList 类中的属性 在 C# 中想要创建动态数组需要使用 ArrayList 类,下表中列出了 Arr