好玩的网站列表

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