数据结构与算法_01_数组

本文介绍最基础的数据结构——数组。

1. 数组理论基础

1.1 一维数组

简单地说，数组是存放在连续内存空间上的相同类型数据的集合。形象地说，它是一组数据，这组数据在内存空间上的存储地址相邻，且这组数据的数据类型相同。如下图所示：

数组可以很方便的通过下标索引的方式获取到下标上对应的数据。上图中可通过下标0获取到数据S、下标3获取到数据J。原理如下：

数组的引用其实就是数组首元素的内存地址，而每一个元素的类型相同，所以占用空间大小一样；那么知道第一个元素内存地址，每个元素占用空间的大小，又知道下标，所以可通过一个数学表达式就可以计算出某个下标上元素的内存地址，直接通过内存地址定位元素，所以数组的检索效率较高。

需要注意的是：

• 数组下标是从0开始的。
• 数组内存空间的地址是连续的。

真实因为数组在内存空间上的地址是连续的，而且数组的元素不能为空，所以我们在删除元素的时候，实际上是将后面的元素向前移位，覆盖掉要删除的元素。而在插入元素的时候，实际上是将后面的元素向后移位，留出空位存储要插入的元素（数组长度需要增加一位）。或者说，数组的元素是不能删的，只能覆盖。如下图所示：

1.2 二维数组

上面提到的数组是一维数组，因为只有一组数据（元素存储的是单个数据）。那么元素可不可以存储一维数组呢？答案是可以的。这样的一维数组称为二维数组。即维度是2，第一维用于索引“外层一维数组的元素（第几个内层一维数组）”，第二维用于索引“内层一维数组的元素”。如下图所示：

那么二维数组在内存空间上的地址是连续的吗？不同语言在内存管理上是不同的，不过可以肯定的是，最内层的一维数组元素是连续的，而外层数组，也就是一维数组之间可能不是连续的。

1.3 Java中的数组

Java中的数组语法如下：

int[] array_01 = new int[5];
int[] array_01 = {12, 34, 56, 13};

2. 数组经典题目

2.1 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例如下：

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1   

提示：

• 你可以假设 nums 中的所有元素是不重复的。
• n 将在 [1, 10000]之间。
• nums 的每个元素都将在 [-9999, 9999]之间。

这个题目比较简单，因为数组中的元素有序，并且没有重复元素，所以利用二分查找比较合适。代码如下：

public static int binarySearch(int[] nums, int goal){

        int start = 0;
        int end = nums.length - 1;

        int mid;

        if(goal < nums[start] || goal > nums[end]){
            return -1;
        }

        while(start <= end){
            // mid = (start + end) / 2;
            mid = start + (end - start) / 2;
            if(nums[mid] == goal){
                return mid;
            }
            else if(nums[mid] < goal){
                start = mid + 1;
            }
            else{
                end = mid - 1;
            }
        }

        return -1;
    }

注意，两个数相加，可能会超过自身数据类型的取值范围，造成数据溢出，使得后续的除以2发生错误。所以为了防止溢出，可以将代码中的 mid = (start + end) /2;换成mid = start + (end - start) / 2;

2.2 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

题目中提到了，只能使用O(1)的空间来辅助完成，而且这道题本质上的意思是将值为非val的元素移动到数组前面。

最简单的方法就是暴力法，双层循环：外层循环遍历数组，内层循环更新数组。如下所示：

public static int removeElement_01(int[] nums, int val){
        int length = nums.length;
    	// 注意循环的条件
        for (int i = 0; i < length; i++) {
            if(nums[i] == val){
                for (int j = i; j < nums.length - 1; j++) {
                    nums[j] = nums[j+1];
                }
                // 注意，因为此时后续的元素向前移动了，所以当前元素就是没有判断的，后续需要重新判断。
                i--;
                length --;
            }
        }

        return length;
}

另外一种方法就是改进内存循环，不一样移动所有元素，可以只将非val值域前面val值交换（或者将前面val值修改为后面非val值）。

public static int removeElement_02(int[] nums, int val){
        int length = nums.length;
        int end;

        for (int i = 0; i < length; i++) {

            end = length - 1;

            if(nums[i] == val){
                length --;
                while(i < end){
                    if(nums[end] == val){
                        end --;
                    }else{
                        nums[i] = nums[end];
                        break;
                    }
                }
            }
        }
        return length;
    }

还有一种方法是采用双指针的方法，一个指针用于遍历数组，另一个指针用于更新当前数组。本质上说，这道题可以用两个数组来做，就是遍历原始数组，如果该元素不是val，那么就将其存储到新数组中。但是此题，对于空间复杂度有要求，不能开辟新数组，所以可以直接覆盖原始数组，即用两个指针来充当两个数组的索引。

public static int removeElement_03(int[] nums, int val){
    	// 新下标，用于记录新数组
        int newIndex = 0;

        for (int oldIndex = 0; oldIndex < nums.length ; oldIndex++) {
            if(val != nums[oldIndex]){
                nums[newIndex] = nums[oldIndex];
                newIndex ++;
            }
        }
        return newIndex;
    }

3. 备注

部分参考代码随想录 (programmercarl.com)。