(java)玩转算法系列-数据结构精讲[学习笔记]（一）不要小瞧数组

Bertha 。 2023-02-16 12:13 1阅读 0赞

前言：  
课程：[玩转算法系列–数据结构精讲 更适合0算法基础入门到进阶（java版）][_0_java]  
此处是个人学习笔记，用作回顾用途

# 不要小瞧数组 #

### 1.使用java中的数组 ###

Main.java：

public class Main {
    
        public static void main(String[] args) {
    
            int[] arr = new int[10];
            for(int i = 0 ; i < arr.length ; i ++)
                arr[i] = i;
    
            int[] scores = new int[]{100, 99, 66};
            for(int i = 0 ; i < scores.length ; i ++)
                System.out.println(scores[i]);
    
            for(int score: scores)
                System.out.println(score);
    
            scores[0] = 96;
    
            for(int i = 0 ; i < scores.length ; i ++)
                System.out.println(scores[i]);
        }
    }

### 2.二次封装属于我们自己的数组，实现增删改查 ###

Array.java:

public class Array {
    
        private int[] data;
        private int size;
    
        // 构造函数，传入数组的容量capacity构造Array
        public Array(int capacity){
            data = new int[capacity];
            size = 0;
        }
    
        // 无参数的构造函数，默认数组的容量capacity=10
        public Array(){
            this(10);
        }
    
        // 获取数组的容量
        public int getCapacity(){
            return data.length;
        }
    
        // 获取数组中的元素个数
        public int getSize(){
            return size;
        }
    
        // 返回数组是否为空
        public boolean isEmpty(){
            return size == 0;
        }
    
        // 向所有元素后添加一个新元素
        public void addLast(int e){
    
    //        if(size == data.length)
    //            throw new IllegalArgumentException("AddLast failed. Array is full.");
    //
    //        data[size] = e;
    //        size ++;
            add(size, e);
        }
    
        // 在所有元素前添加一个新元素
        public void addFirst(int e){
            add(0, e);
        }
    
        // 在index索引的位置插入一个新元素e
        public void add(int index, int e){
    
            if(size == data.length)
                throw new IllegalArgumentException("Add failed. Array is full.");
    
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    
            for(int i = size - 1; i >= index ; i --)
                data[i + 1] = data[i];
    
            data[index] = e;
    
            size ++;
        }
    
    }

Main.java:

public class Main {
    
        public static void main(String[] args) {
    
    		Array arr = new Array(20);
    		for(int i=0;i<10;i++)
    			arr.addLast(i);
    		System.out.println(arr);
    		
    		arr.add(1,100);
    		System.out.println(arr);
    			
    		arr.addFirst(-1);
    		System.out.println(arr);
    		
    		arr.remove(2);
    		System.out.println(arr);
    		
    		arr.removeElemet(4);
    		System.out.println(arr);
    		
    		arr.removeFirst();
    		System.out.println(arr);
    		}
    }

### 3.使用泛式 ###

**泛型类和泛型接口**

如果定义的一个类或接口有一个或多个类型变量，则可以使用泛型。泛型类型变量由尖括号界定，放在类或接口名的后面，下面定义尖括号中的T称为类型变量。意味着一个变量将被一个类型替代替代类型变量的值将被当作参数或返回类型。  
Array.java（在2的基础上改代码，\*为修改位置）：

public class Array<E> { *
    
        private E[] data; *
        private int size;
    
        // 构造函数，传入数组的容量capacity构造Array
        public Array(int capacity){
            data = (E[])new Object[capacity];*
            size = 0;
        }
    
        // 无参数的构造函数，默认数组的容量capacity=10
        public Array(){
            this(10);
        }
    
        // 获取数组的容量
        public int getCapacity(){
            return data.length;
        }
    
        // 获取数组中的元素个数
        public int getSize(){
            return size;
        }
    
        // 返回数组是否为空
        public boolean isEmpty(){
            return size == 0;
        }
    
        // 在index索引的位置插入一个新元素e
        public void add(int index, E e){*
    
            if(size == data.length)
                throw new IllegalArgumentException("Add failed. Array is full.");
    
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    
            for(int i = size - 1; i >= index ; i --)
                data[i + 1] = data[i];
    
            data[index] = e;
    
            size ++;
        }
    
        // 向所有元素后添加一个新元素
        public void addLast(E e){*
            add(size, e);
        }
    
        // 在所有元素前添加一个新元素
        public void addFirst(E e){*
            add(0, e);
        }
    
        // 获取index索引位置的元素
        public E get(int index){*
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Get failed. Index is illegal.");
            return data[index];
        }
    
        // 修改index索引位置的元素为e
        public void set(int index, E e){*
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Set failed. Index is illegal.");
            data[index] = e;
        }
    
        // 查找数组中是否有元素e
        public boolean contains(E e){*
            for(int i = 0 ; i < size ; i ++){
                if(data[i].equals(e))
                    return true;
            }
            return false;
        }
    
        // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
        public int find(E e){*
            for(int i = 0 ; i < size ; i ++){
                if(data[i].equals(e))
                    return i;
            }
            return -1;
        }
    
        // 从数组中删除index位置的元素, 返回删除的元素
        public E remove(int index){*
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Remove failed. Index is illegal.");
    
            E ret = data[index];*
            for(int i = index + 1 ; i < size ; i ++)
                data[i - 1] = data[i];
            size --;
            data[size] = null; // loitering objects != memory leak *
            return ret;
        }
    
        // 从数组中删除第一个元素, 返回删除的元素
        public E removeFirst(){
            return remove(0);
        }
    
        // 从数组中删除最后一个元素, 返回删除的元素
        public E removeLast(){*
            return remove(size - 1);
        }
    
        // 从数组中删除元素e
        public void removeElement(E e){*
            int index = find(e);
            if(index != -1)
                remove(index);
        }
    
        @Override
        public String toString(){
    
            StringBuilder res = new StringBuilder();
            res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
            res.append('[');
            for(int i = 0 ; i < size ; i ++){
                res.append(data[i]);
                if(i != size - 1)
                    res.append(", ");
            }
            res.append(']');
            return res.toString();
        }
    }

Main.java：

public class Main {
    
        public static void main(String[] args) {
    
            Array<Integer> arr = new Array<>(20);
            for(int i = 0 ; i < 10 ; i ++)
                arr.addLast(i);
            System.out.println(arr);
    
            arr.add(1, 100);
            System.out.println(arr);
    
            arr.addFirst(-1);
            System.out.println(arr);
            // [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    
            arr.remove(2);
            System.out.println(arr);
    
            arr.removeElement(4);
            System.out.println(arr);
    
            arr.removeFirst();
            System.out.println(arr);
        }
    }

Student.java：

public class Student {
    
        private String name;
        private int score;
    
        public Student(String studentName, int studentScore){
            name = studentName;
            score = studentScore;
        }
    
        @Override
        public String toString(){
            return String.format("Student(name: %s, score: %d)", name, score);
        }
    
        public static void main(String[] args) {
    
            Array<Student> arr = new Array<>();
            arr.addLast(new Student("Alice", 100));
            arr.addLast(new Student("Bob", 66));
            arr.addLast(new Student("Charlie", 88));
            System.out.println(arr);
        }
    }

### 4.动态数组 ###

Java动态数组是一种可以任意伸缩数组长度的对象  
![在这里插入图片描述][20200609220058441.png]  
变成：  
![在这里插入图片描述][20200609220133567.png]  
Array.java：  
（在3的基础上改代码，修改了add()函数和增加了resize()函数,并相应修改了remove()，用//----标明）

public class Array<E> {
    
        private E[] data;
        private int size;
    
        // 构造函数，传入数组的容量capacity构造Array
        public Array(int capacity){
            data = (E[])new Object[capacity];
            size = 0;
        }
    
        // 无参数的构造函数，默认数组的容量capacity=10
        public Array(){
            this(10);
        }
    
        // 获取数组的容量
        public int getCapacity(){
            return data.length;
        }
    
        // 获取数组中的元素个数
        public int getSize(){
            return size;
        }
    
        // 返回数组是否为空
        public boolean isEmpty(){
            return size == 0;
        }
        
    //---------------------------------------------------------------------------------------------------------
        // 在index索引的位置插入一个新元素e
        public void add(int index, E e){
    
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    
            if(size == data.length)
                resize(2 * data.length);
    
            for(int i = size - 1; i >= index ; i --)
                data[i + 1] = data[i];
    
            data[index] = e;
    
            size ++;
        }
    //---------------------------------------------------------------------------------------------------------
    
    
        // 向所有元素后添加一个新元素
        public void addLast(E e){
            add(size, e);
        }
    
        // 在所有元素前添加一个新元素
        public void addFirst(E e){
            add(0, e);
        }
    
        // 获取index索引位置的元素
        public E get(int index){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Get failed. Index is illegal.");
            return data[index];
        }
    
        // 修改index索引位置的元素为e
        public void set(int index, E e){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Set failed. Index is illegal.");
            data[index] = e;
        }
    
        // 查找数组中是否有元素e
        public boolean contains(E e){
            for(int i = 0 ; i < size ; i ++){
                if(data[i].equals(e))
                    return true;
            }
            return false;
        }
    
        // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
        public int find(E e){
            for(int i = 0 ; i < size ; i ++){
                if(data[i].equals(e))
                    return i;
            }
            return -1;
        }
    
    //---------------------------------------------------------------------------------------------------------
        // 从数组中删除index位置的元素, 返回删除的元素
        public E remove(int index){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Remove failed. Index is illegal.");
    
            E ret = data[index];
            for(int i = index + 1 ; i < size ; i ++)
                data[i - 1] = data[i];
            size --;
            data[size] = null; // loitering objects != memory leak
    
            if(size == data.length / 2)
                resize(data.length / 2);
            return ret;
        }
    //---------------------------------------------------------------------------------------------------------
    
        // 从数组中删除第一个元素, 返回删除的元素
        public E removeFirst(){
            return remove(0);
        }
    
        // 从数组中删除最后一个元素, 返回删除的元素
        public E removeLast(){
            return remove(size - 1);
        }
    
        // 从数组中删除元素e
        public void removeElement(E e){
            int index = find(e);
            if(index != -1)
                remove(index);
        }
    
        @Override
        public String toString(){
    
            StringBuilder res = new StringBuilder();
            res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
            res.append('[');
            for(int i = 0 ; i < size ; i ++){
                res.append(data[i]);
                if(i != size - 1)
                    res.append(", ");
            }
            res.append(']');
            return res.toString();
        }
    
    //---------------------------------------------------------------------------------------------------------
        // 将数组空间的容量变成newCapacity大小
        private void resize(int newCapacity){
    
            E[] newData = (E[])new Object[newCapacity];
            for(int i = 0 ; i < size ; i ++)
                newData[i] = data[i];
            data = newData;
        }
    //---------------------------------------------------------------------------------------------------------
    }

Main.java:

public class Main {
    
        public static void main(String[] args) {
    
            Array<Integer> arr = new Array<>();
            for(int i = 0 ; i < 10 ; i ++)
                arr.addLast(i);
            System.out.println(arr);
    
            arr.add(1, 100);
            System.out.println(arr);
    
            arr.addFirst(-1);
            System.out.println(arr);
    
            arr.remove(2);
            System.out.println(arr);
    
            arr.removeElement(4);
            System.out.println(arr);
    
            arr.removeFirst();
            System.out.println(arr);
        }
    }

### 5. 通过时间复杂度分析优化代码 ###

**简单时间负责度分析**  
![在这里插入图片描述][20200611093043495.png]  
![在这里插入图片描述][20200611093124757.png]

·增：O（n）  
·删：O（n）  
·改：已知索引O（1）； 未知索引O（n）  
·查：已知索引O（1）；未知索引O（n）

**resize的复杂度分析**  
假设当前capacity=8，并且每一次添加操作都使用addLast  
9次addLast操作，触发resize，总共进行了17次基本操作  
**平均**每次addLast操作，进行2次基本操作

假设capacity=n，n+1次addLast，触发resize，总共进行2n+1次基本操作  
**平均**每次addLast操作，进行2次基本操作  
这样**均摊计算**，时间复杂度是O（1）的  
同理，removeLast操作**均摊复杂度**也为O（1）

但是。当我们同时看addLast和removeLast操作，会出现**复杂度震荡**：  
当capacity=n时，  
添加元素，需要扩容，复杂度为O(n),  
删除元素，需要缩容，复杂度为O(n)

出现问题的原因：removeLast 时 resize 过于着急（Eager）  
解决方案：当size==capacity/4时，才将capacity减半（Lazy）

Array.java（修改remove()，\*为修改位置)：

// 从数组中删除index位置的元素, 返回删除的元素
        public E remove(int index){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Remove failed. Index is illegal.");
    
            E ret = data[index];
            for(int i = index + 1 ; i < size ; i ++)
                data[i - 1] = data[i];
            size --;
            data[size] = null; // loitering objects != memory leak
    
            if(size == data.length / 4 && data.length / 2 != 0) *
                resize(data.length / 2);
            return ret;
        }

[_0_java]: https://coding.imooc.com/class/207.html
[20200609220058441.png]: https://img-blog.csdnimg.cn/20200609220058441.png
[20200609220133567.png]: https://img-blog.csdnimg.cn/20200609220133567.png
[20200611093043495.png]: https://img-blog.csdnimg.cn/20200611093043495.png
[20200611093124757.png]: https://img-blog.csdnimg.cn/20200611093124757.png