数组:把数据码成一排进行存放
public class array { 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]); // 数组可遍历 scores[0] = 98; for (int score: scores) System.out.println(score); } }
数组最大的优点:快速查询 score[2]
数组最好应用于“索引有语意”的情况
但并非所有有语意的索引都适合用于数组,例如身份证号
数组也可以处理“索引没有语意”的情况,这里主要处理“索引没有语义”的情况数组的使用
public class array { private int[] data; private int size; // 构造函数,传入数组的容量capacity构造array public array(int capacity){ data = new int[capacity]; size = 0; } // 无参数的构造函数,默认数组容量capaciay=10 public array(){ this(10); } // 获取数组中的元素个数 public int getSize(){ return size; } // 获取数组的容量 public int getCapacity(){ return data.length; } // 判断数组是否为空 public boolean isEmpty(){ return size == 0; } }
向数组末尾添加元素,还是在上面的类中添加方法
// 向所有元素后添加一个新元素 public void addList(int e){ // 如果元素的个数等于数组的容量,那么抛出异常 if (size == data.length) throw new IllegalArgumentException("AddLast failed. array is full"); data[size] = e; size++; }
指定位置添加元素
// 在第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. array is full"); } for (int i = size - 1; i >= index; i--){ data[i+1] = data[i]; } data[index] = e; size++; }
在元素前面添加一个新元素
// 在所有元素前添加一个新元素 public void addFirst(int e){ add(0,e); }
还是在上面的类中写方法,这里重写toString方法,用于查询元素
@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(); }
获取元素以及修改元素
// 获取index索引位置的元素 int get(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("GET failed. array is full"); return data[index]; } // 修改index索引位置的元素e void set (int index,int e){ if (index < 0 || index >= size) throw new IllegalArgumentException("set failed. array is full"); data[index] = e; }
把前面写的功能进行测试
public class Main { public static void main(String[] args ){ array arr = new array(20); for (int i = 0 ; i < 10 ; i++){ arr.addList(i); } System.out.println(arr); // 索引为1的位置添加100 arr.add(1,100); System.out.println(arr); // 开始添加-1 arr.addFirst(-1); System.out.println(arr); } } // 打印结果 array: size = 10 , capacity = 20 [0,1,2,3,4,5,6,7,8,9] array: size = 11 , capacity = 20 [0,100,1,2,3,4,5,6,7,8,9] array: size = 12 , capacity = 20 [-1,0,100,1,2,3,4,5,6,7,8,9]
还是在上面的类中写方法,包含
// 查找数组中是否有元素e public boolean contains(int e){ for (int i = 0 ; i < size ; i++){ if (data[i] == e){ return true; } } return false; }
搜索
// 查找数组中元素e所在的索引,如果元素不存在,返回-1 public int find(int e){ for (int i = 0 ; i < size ; i++){ if (data[i] == e){ return i; } } return -1; }
删除
// 从数组中删除index位置的元素,返回删除的元素 public int remove(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("Remove failed"); int ret = data[index]; for (int i = index + 1 ; i < size ; i++) data [ i - 1] = data[i]; // 这个地方需要注意 size --; return ret; } // 从数组中删除第一个元素,返回删除的元素 public int removeFirst(){ return remove(0); } // 从数组中删除最后一个元素,返回删除的元素 public int removeLast(){ return remove(size - 1); } // 从数组中删除元素e public void removeElement(int e){ int index = find(e); if (index != -1){ remove(index); } }
进行测试
public class Main { public static void main(String[] args ){ array arr = new array(20); for (int i = 0 ; i < 10 ; i++){ arr.addList(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(); arr.removeLast(); System.out.println(arr); } } array: size = 10 , capacity = 20 [0,1,2,3,4,5,6,7,8,9] array: size = 11 , capacity = 20 [0,100,1,2,3,4,5,6,7,8,9] array: size = 12 , capacity = 20 [-1,0,100,1,2,3,4,5,6,7,8,9] array: size = 11 , capacity = 20 [-1,0,1,2,3,4,5,6,7,8,9] array: size = 10 , capacity = 20 [-1,0,1,2,3,5,6,7,8,9] array: size = 8 , capacity = 20 [0,1,2,3,5,6,7,8]
基本功能已经实现,但是还是有很多需要完善的地方。
public class array<E> { // 数据类型由之前的int改成现在的 private E[] data; private int size; // 构造函数,传入数组的容量capacity构造array // 这里使用了强制类型转化 public array(int capacity){ data = (E[]) new Object[capacity]; size = 0; } // 无参数的构造函数,默认数组容量capaciay=10 public array(){ this(10); } // 获取数组中的元素个数 public int getSize(){ return size; } // 获取数组的容量 public int getCapacity(){ return data.length; } // 判断数组是否为空 public boolean isEmpty(){ return size == 0; } // 向所有元素后添加一个新元素,转入参数类型改变 public void addLast(E e){ // 如果元素的个数等于数组的容量,那么抛出异常 if (size == data.length) throw new IllegalArgumentException("AddLast failed. array is full"); data[size] = e; size++; } // 在所有元素前添加一个新元素,转入参数类型改变 public void addFirst(E e){ add(0,e); } // 在第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. array is full"); } for (int i = size - 1; i >= index; i--){ data[i+1] = data[i]; } data[index] = e; size++; } @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(); } // 获取index索引位置的元素,返回类型改变 E get(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("GET failed. array is full"); return data[index]; } // 修改index索引位置的元素e,转入参数类型改变 void set (int index,E e){ if (index < 0 || index >= size) throw new IllegalArgumentException("set failed. array is full"); 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所在的索引,如果元素不存在,返回-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"); E ret = data[index]; for (int i = index + 1 ; i < size ; i++) data [ i - 1] = data[i]; size --; // data[size] = null; // loitering objects 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); } } }
为了进行测试,从新建一个Student类来进行测试,这样就可以使用任意类型的数据
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)/n",name,score); } public static void main(String[] args){ // 使用泛型 array<Student> arr = new array<>(); arr.addLast(new Student("Alice",100)); arr.addLast(new Student("Bob",88)); arr.addLast(new Student("Char",66)); System.out.println(arr); } } 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)/n",name,score); } public static void main(String[] args){ // 使用泛型 array<Student> arr = new array<>(); arr.addLast(new Student("Alice",100)); arr.addLast(new Student("Bob",88)); arr.addLast(new Student("Char",66)); System.out.println(arr); } } array: size = 3 , capacity = 10 [Student(name: Alice , score: 100) ,Student(name: Bob , score: 88) ,Student(name: Char , score: 66) ]
说明还是成功的,由于int类型太单调,之后都将使用泛型来进行操作
由于数组是由限制的,在用户不知道数据的个数的时候,容易抛出异常,这个时候就要使用动态数组,而不用再考虑数据的个数
具体的实现,还是在array类中
// 动态数组 private void resize(int newCapacity){ // 使用泛型,强制类型转换 E[] newData = (E[])new Object[newCapacity]; // 把之前数组中的数据传到新的数组中 for (int i = 0 ; i < size ; i ++){ newData[i] = data[i]; } //新的数组再指向到原来的数组,狸猫换太子 data = newData; }
把添加元素的方法进行改写,
public void add(int index,E e){ // 如果数组已经满了 if (size == data.length) // throw new IllegalArgumentException("Add failed. array is full"); // 调用动态数组,扩容到之前容量的二倍 resize(2 * data.length); if (index < 0 || index > size){ throw new IllegalArgumentException("Add failed. array is full"); } for (int i = size - 1; i >= index; i--){ data[i+1] = data[i]; } data[index] = e; size++; }
把删除元素的方法也进行改写
public E remove(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("Remove failed"); E ret = data[index]; for (int i = index + 1 ; i < size ; i++) data [ i - 1] = data[i]; size --; // data[size] = null; // loitering objects // 如果数组中剩余的数量是数组长度的二倍,那么就把数组的长度减半 if (size == data.length / 2) resize(data.length / 2); return ret; }
进行测试
public class Main { public static void main(String[] args ){ // int类型的包装类 array<Integer> arr = new array<>(5); for (int i = 0 ; i < 5 ; 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(); arr.removeLast(); System.out.println(arr); } } array: size = 5 , capacity = 5 [0,1,2,3,4] 当数据多的时候,自动扩容的之前的两倍 array: size = 6 , capacity = 10 [0,100,1,2,3,4] array: size = 7 , capacity = 10 [-1,0,100,1,2,3,4] array: size = 6 , capacity = 10 [-1,0,1,2,3,4] 当数据少的时候,自动缩少两倍 array: size = 5 , capacity = 5 [-1,0,1,2,3] array: size = 3 , capacity = 5 [0,1,2]
这样就基本实现了动态的数组
public static int sum(int[] nums){ int sun = 0; for(int num: nums) sum += num; return sum; }
这里算法是O(n),这里n是nums中元素的个数
也就是说这个算法运行的时间的多少和这里的nums中元素的个数呈线性关系,也就是nums中的个数越多时间就越多
为什么要用大O,叫做O(n)?忽略常数,实际时间(线性)
$$
T = c1*n + c2
$$
具体分析算法的时候就直接忽略常数, 渐进时间复杂度,描述n趋近于无穷的情况
T = 2*n + 2 | O(n) |
T = 2000*n + 1000 | O(n) |
T = n n 1 + 0 | O(n^2) |
T = 2 n n + 300*n + 10 | O(n^2) |
向数组头添加元素的时候,要把数组中的每一个元素往后面移动,所以是O(n),整体来看, 通常做最坏的打算 ,也是O(n),添加的还有注意resize方法
添加操作 | O(n) |
---|---|
addLast(e) | O(1) |
addFirst(e) | O(n) |
add(index,e) | O(n/2) = O(n) |
resize | O(n) |
删除操作和上面的一样,也是做最坏的打算,也是O(n),删除时还要注意resize方法
删除操作 | O(n) |
---|---|
removeLast(e) | O(1) |
removeFirst(e) | O(n) |
remove(index,e) | O(n/2) = O(n) |
修改操作,这个是最简单的,O(1)
修改操作 | O(1) |
---|---|
set(index,e) | O(1) |
查找操作,也是O(n)
查找操作 | O(n) |
---|---|
get(index) | O(1) |
contains(e) | O(n) |
find(e) | O(n) |
总结
增 | O(n) |
删 | O(n) |
改 | 已知索引O(1),未知索引O(n) |
查 | 已知索引O(1),未知索引O(n) |
从最坏的方面来看, addLast(e)的复杂度是O(1) ,如果此时数组容量不够需要扩容的时候就要调用resize方法, 但是resize方法的复杂度是O(n) ,所以综合来说 addLast(e)的复杂度是O(n) ,但是也不是每一次添加就会扩容,所以用最坏的来分析有点不合理,这里用到下面的知识了
假设当前的capacity = 8 ,并且每一次添加操作都使用addLast
$$
1+1+1+1+1+1+1+1+8+1
$$
9次addLast操作,触发resize,总共进行了17次的基本操作,9次添加,8次转移,
平均来说也就是每次addLast操作,进行了大约两次基本操作
所以在这个例子中,均摊计算,比计算最坏情况有意义
addLast的均摊复杂度是O(1)
同理,removeLast的均摊复杂度也是O(1)
但是,我们同时来看addLast和removeLast操作
当capacity = n时,调用addLast,这里进行扩容,复杂度O(n),然后执行removeLast,进行缩容,复杂度也是O(n),如此循环,复杂度就一直是O(n)了
出现问题的原因:removeLast是resize过于着急(Eager),不必一下子就缩容
解决方案:Lazy,当数据是总长度的1/4时进行缩容,缩容还是变回原来的一半
当size == capacity /4 时,才将capacity减半
通过这样的方法,就解决了复杂度震荡的问题
下面用代码实现,还是在array类中修改,把remove方法改写就可以了,
public E remove(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("Remove failed"); E ret = data[index]; for (int i = index + 1 ; i < size ; i++) data [ i - 1] = data[i]; size --; // data[size] = null; // loitering objects // 这里等于1/4的才进行缩容,但是还要注意长度除于2不能等于0 if (size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2); return ret; }