数据结构与算法(3)-数组

  1. 1. 什么是数组
  2. 2. 数组的插入,删除,随机访问
  3. 3. 数组的访问越界问题
  4. 4. 容器 vs 数组
  5. 5. 为什么数组要从0开始编号?
  6. 6. 算法实战
    1. 6.1 3Sum

1. 什么是数组

  • 是一种线性表数据结构,用一组连续的内存空间,来存储一组具有相同类型的数据
  • 线性表
    • 数据排成了线性的结构
    • 每个线性表上的数据只有前后两个方向
    • 除了数组,链表、队列、栈等也是线性表结构
  • 非线性表
    • 比如说二叉树,堆,图等 他们的数据之间不是简单的前后关系了
  • 连续内存空间与相同类型的数据
    • 正因为有这个特征其才可以进行随机访问
    • 但是这也导致了想要在数组当中删除,插入一个数据,为了保证连续性,就需要做大量的数据搬移工作
    • 数组非常适合根据下标来进行访问
  • 线性表 - 数组
    • 表中的数据只有前后两个方向
    • 数组,链表,队列,栈都是线性表结构
  • 非线性表
    • 二叉树,堆,图
    • 数据之间并不是简单的前后关系

2. 数组的插入,删除,随机访问

  • 插入,删除
    • 在k位置做操作,那么对于k位置之后的k - n都是需要做移位的
  • 删除的优化
    • 避免每次删除都直接的搬移数据
    • 先记录下已经删除的数据
    • 每次删除操作并不是真正搬移数据,只是记录数据已经被删除了
    • 当数组没有更多空间存储了以后,再触发执行一次真正的删除操作
    • 通过这种方式大大减少了删除操作导致的数据搬移
    • —–> JVM标记清除垃圾回收算法

3. 数组的访问越界问题

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

当i=3的时候,访问越界。在C语言当中,只要不是访问受限的内存,内存空间都是可以自由访问的。a[3]会被定位到某块不属于数组的内存地址上,而这个地址正好是存储变量i的内存地址,那么arr[3] = 0 就相当于 i=0,因此会导致代码无限循环。

对这里的无限循环的解释:函数体内的局部变量存在栈上,且是连续压栈。在Linux进程的内存布局中,栈区在高地址空间,从高向低增长。变量i和arr在相邻地址,且i比arr的地址大,所以arr越界正好访问到i。当然,前提是i和arr元素同类型,否则那段代码仍是未决行为。

数组越界是一种未决行为,并没有规定数组访问越界时编译器应该如何处理。因为,访问数组的本质就是访问一段连续内存,只要数组通过偏移计算得到的内存地址是可用的,那么程序就可能不会报任何错误。

Java做了封装,会判断出数组越界的行为,并throw exception。

4. 容器 vs 数组

容器,譬如Java中的ArrayList,最大优势是可以将许多数组操作细节封装起来。另外,其支持动态扩容。动态扩容很耗时的,因为牵扯到内存申请,还有整体的数据搬移。因此如果能确定需要村塾的数据的大小,最好在创建Arraylist的时候事先指定好

  • 使用数组的情况
    • ArrayList 无法存储基本类型,需要封装,autoBoxing, unboxing本身是有一定的性能消耗的,如果特别关注性能,那么我们就需要用数组
    • 如果数组大小已知,并且对数据的操作很简单。不需要使用ArrayList所提供的大部分的方法,那么我们可以直接使用数组
    • 多维数组的表示会更为直观一些

5. 为什么数组要从0开始编号?

因为下标最确切的定义是偏移,offset。要算a[k]的内存地址的公式为:

a[k]_address = base_address + k * type_size

如果我们从1开始计数,那么我们计算位置的公式就会变成:

a[k]_address = base_address + (k-1)*type_size

这样每次访问都会多一次减法运算!!!对于CPU来说,就是多了一次减法指令。从0开始就是为了提高效率,当然这个效率的提升其实很小,也有一大部分是历史原因了,即不同语言的迁移之间的学习成本。

6. 算法实战

6.1 3Sum

题目的详述见上方的连接,思路的话首先最直观的方式一定是三层循环,来确定出所有的解,brute force的方式很慢,O(n^3)谁受得了。

按照分治的观点,我们可以先思考下2Sum应该如何实现,有没有什么方便的办法。2Sum的话,我们可以选择先排序,然后选两个初始点,即最左(最小)和最右(最大),根据每次得出的结果来更新两个坐标的位置,最终拿到结果,这样的大O复杂度为O(nlogn).按照这种思路的代码实现如下:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();

        if (nums.length < 3) {
            return ans;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length -2; i ++) {
            if (i == 0 || i != 0 && nums[i] != nums[i - 1]) {
                int low = i+1;
                int high = nums.length - 1;

                while (high > low) {
                    if (nums[i] + nums[low] + nums[high] > 0) {
                        high --;
                    } else if (nums[i] + nums[low] + nums[high] < 0) {
                        low ++;
                    } else {
                        ans.add(Arrays.asList(nums[i], nums[low], nums[high]));
                        while(low < high && nums[low] == nums[low+1]) low++;
                        while(low < high && nums[high] == nums[high-1]) high--;
                        low ++;
                        high --;
                    }
                }
            }
        }

        return ans;
    }
}

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:数据结构与算法(3)-数组

文章字数:1.4k

本文作者:Leilei Chen

发布时间:2020-02-09, 14:46:35

最后更新:2020-04-29, 03:00:46

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-3-%E6%95%B0%E7%BB%84/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏