从本篇勾勾开始学习数据结构，主要是了解一些数据结构的概念，掌握常用的数据结构，以便在开发中能根据不同的业务场景选择合适的数据结构。

一道算法题

我们首先看Leetcode第26题：

26. 删除排序数组中的重复项

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 :

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

解题要求：

1. 不能使用额外的空间，即不能创建新的对象，只能在当前数组上做修改
2. 只要求返回新的数组长度，所以我们可以不关心里面的元素具体怎么样排列的，只需要返回不重复的元素个数就可以
3. 复杂度要求O(1)，即你不能一遍遍的遍历数组

那怎么办呢？要做出来这道算法题，我们需要对数据特别了解。

接下来和勾勾一起解开它吧！

数组的初始化

数组是Java中效率最高的存储和随机访问对象引用序列的方式，它其实就是一个简单的线性序列。为了实现访问的高效率，数组的大小必须是固定的，而且在数组的整个生命周期中不能改变。

数组中的元素可以是基本数据类型也可以是引用类型，不管是哪种数据结构，数组标识符都是一个执行堆内存中真实对象的一个引用。

定义一个数组有如下几种方式：

 public static void main(String[] args) {
        int[] intArr;
        int intArr2[];
        int[] intArr3 = new int[10];
        int[] intArr4 = {1, 2, 3, 4};
        int[] intArr5 = new int[]{1, 2, 3, 4};
        intArr = intArr4;
        System.out.println(intArr3[0]);
        System.out.println(intArr[0]);
        System.out.println(intArr4[0]);
        intArr4[0] = 5;
        System.out.println(intArr[0]);
        System.out.println(intArr4[0]);
    }

intArr 和 intArr2[] 只是两种不同的书写习惯，含义是相同的，勾勾更喜欢第一种，比较形象直观一点。未进行初始化的数组是不能够直接使用的。

如果不知道里面需要放哪些元素，可以使用new的方式在数据中创建元素，元素的值为数据类型的初始化值（引用类型为null，数字和字符为0，布尔类型为false）。

如果我们已经明确知道数组中的元素值，也可以像intArr4和intArr5一样初始化数组。

intArr 、intArr3、intArr4打印第一个元素，修改intArr4的第一个元素为5之后再次输出：

0
1
1
5
5

我们修改了intArr4中的元素，intArr引用中的元素也变了，我们看一下intArr 、intArr3、intArr4在内存中的情况：

intArr = intArr4;这个操作只是复制了一份引用，他们两个公共指向了堆中的同一块内存区域，所以修改数据，两个引用获取到的数据都会变化。

我们上述示例中输出时用的是intArr[下标值]，这个语法是访问数组对象的唯一的方式。

数组的使用

length属性

数组对象除了包含一个指定堆内存的引用之外，还有一个只读成员length，它表示此数组对象可以存储多少元素。

String[] nameArr = new String[]{"CodeGirl", "JJ"};
System.out.println("nameArr数组的长度length=" + nameArr.length);
Character[] charArr = {'C', 'o', 'd', 'e'};
System.out.println("charArr数组的长度length=" + charArr.length);
Integer[] integerArr = new Integer[10];
System.out.println("integerArr数组的长度length=" + integerArr.length);

打印的结果为：

nameArr数组的长度length=2
charArr数组的长度length=4
integerArr数组的长度length=10

通过数组的length属性我们可以判断数组中是否包含元素，做一些边界的校验。

length属性只表示数组中能够容纳的元素的个数，并不表示现在数组中有多少个元素，这也是数组的一个缺点，我们无法明确的知道数组中有多少元素。

Arrays工具类库

java.util.Arrays类提供了很多适用于数组的static方法，包含数组排序sort()、两个数组比较是否相等equals()、将数组转换为String表示toString()、转换为List结构asList()等其他方法，我们通过例子简单了解下，大家还需在平时的练习中熟练掌握。

       String[] strArr = new String[]{"Java", "Code"};
        String[] strArr2 = {"JAVA", "CODE"};
        /**
         * 打印数组元素
         */
        System.out.println("strArr元素为："+Arrays.toString(strArr));
        System.out.println("strArr2元素为："+Arrays.toString(strArr2));
        /**
         * 判断两个数组是否相等
         */
        System.out.println("strArr和strArr2两个数组是否相等：" + Arrays.equals(strArr, strArr2));
        String[] strArr3 = new String[2];
        /**
         * 复制数组
         */
        strArr3 = Arrays.copyOf(strArr, 2);
        System.out.println("strArr3元素为："+Arrays.toString(strArr3));
        System.out.println("strArr和strArr3两个数组是否相等：" + Arrays.equals(strArr, strArr3));
        strArr3[0] = "Java01";
        System.out.println("strArr3元素为："+Arrays.toString(strArr3));
        System.out.println("strArr和strArr3两个数组是否相等：" + Arrays.equals(strArr, strArr3));
        /**
         * 元素排序:默认升序
         */
        int[] intArr = {4, 1, 9, 8};
        Arrays.sort(intArr);
        System.out.println("intArr排序后：" + Arrays.toString(intArr));

        /**
         * 将数组转换为List
         */
        List<String> list = Arrays.asList(strArr);

        /**
         * 将字符串转换为数组
         */
        String str = "HelloWorld";
        char[] charArr = str.toCharArray();
        System.out.println("charArr中的数组元素："+Arrays.toString(charArr));

在这里我们要注意：

• Arrays.copyOf并不是复制引用，而是复制了堆内的数据结构。这里我们引入两个概念深复制和浅复制。

深复制：增加了指针，并且申请了新的内存，新增的指针指向了这个内存。

浅复制：只是增加了指针指向了内存中已经存在的内存地址。

• Arrays.equals在比较两个数组时，数据的元素个数必须相等，并且对应位置的元素也要相等。

操作数组

数组的操作包括数据的增加、修改和遍历。

数组是内存中一块连续的区域，它的操作可以通过下标进行，下标从0开始。

可以通过数组下标直接获取元素，添加元素都是添加到最后。

一般不会删除元素而是使用其他元素修改下标位置的值。

 char[] charArr = new char[10];
 //添加
 charArr[0] = 'H';
 charArr[1] = 'L';
 System.out.println("charArr的元素为："+Arrays.toString(charArr));
 //修改
 charArr[1] = 'M';
 System.out.println("charArr的元素为："+Arrays.toString(charArr));
 //删除
 charArr[1] = 0;      
 System.out.println("charArr的元素为："+Arrays.toString(charArr));
  //遍历
 for (int i = 0; i < charArr.length; i++) {
     System.out.println(charArr[i]);
 }

如果下标i的值超过了数组的边界值，则会报错ArrayIndexOutOfBoundsException。

算法题解答

到这里我们已经了解了数组，接下来我们解决这道算法题目吧！

class Solution {
    public int removeDuplicates(int[] nums) {
        //先做参数校验，如果没有元素直接返回0
        if(nums.length == 0){
            return 0;
        }
        //初始化两个指针i和j，i从第一个元素开始，J从i+1个元素开始
        int i = 0;
        //遍历数组
        for(int j = 1; j<nums.length; j++){
            //通过下标获取元素，如果两个元素不相等，则i向后移动，这个数组是排序数组，如果不是排序数组此处不成立
            if(nums[i] != nums[j]){
                i++;
                nums[i] = nums[j];
            }
        }
        //i从0开始，返回时需要+1
        return i+1;
    }
}

好了，数组就学到这里了！

我是勾勾，一直在努力的程序媛，感谢您的点赞、关注和转发！

下一篇：一道算法题的思考之List集合