数组
-
静态数组：是一块连续的内存空间，可以通过索引来访问这块内存空间的元素，是数组的原始形态
-
动态数组：是编程语言为了我们方便使用，在静态数组的基础上添加了常用的api，如push、insert、remove等方法，可以让我们不用写代码去实现操作
定义一个静态数组
package com.wang.base.array;
public class Demo01 {
//少了psvm
//定义一个大小为10的静态数组和名字为arr的数组指针，指向这段内存空间的首地址
int[] arr=new int[10];//在内存中开辟了一段连续的内存空间，大小是10*4个字节
//使用索引赋值
arr[0]=1;
arr[1]=2;
//使用索引取值
int a=arr[0];
}
int arr[10]语句中我们可以知道：
- 内存空间的首地址：arr指向首地址
- 每个元素类型：int，每个元素占用内存空间大小为4个字节
- 这块空间是连续的，大小为10*4=40个字节
所以我们获得了数组的超能力：随机访问，只要给定任何一个数组索引，我们可以在O(1)时间内直接获取到对应元素的值
O(1)是因为计算机的内存寻址时间可以认为是O(1)
增：给静态数组增加元素
情况一：数组末尾追加（append）元素
package com.wang.base.array;
public class Demo01 {
public static void main(String[] args) {
//大小为10的数组已经装了4个元素
int[]arr=new int[10];
for (int i = 0; i < 4; i++) {
arr[i]=i;
}
//现在在数组末尾追加元素4和5
arr[4]=4;
arr[5]=5;
//以此类推。。。
}
}
由于只是对索引赋值，所以在数组末尾追加元素的时间复杂度是O(1)
情况二：数组中间插入（insert）元素
package com.wang.base.array;
public class Demo01 {
public static void main(String[] args) {
//大小为10的数组已经装了4个元素
int[]arr=new int[10];
for (int i = 0; i < 4; i++) {
arr[i]=i;
}
//想在第三个位置插入元素666，即arr【2】=666
//需要把第三个位置及后面的元素都向后移动一位
//注意要倒着遍历数组中已有元素，避免覆盖
for (int i = 4; i > 2; i--) {
arr[i]=arr[i-1];
}
arr[2]=666;
}
}
综上，在数组中间插入元素的时间复杂度是O(N),因为涉及到数据搬迁，给新元素腾地方
情况三：数组空间已满
连续空间必须一次性分配，分配好之后不能随意删减（因为后面可能已经被其他程序占用了，不能说你想要就给你）
所以只能重新申请更大一块的空间，把原来的数据复制过去，再加入新元素，这就是数组的扩容操作
package com.wang.base.array;
public class Demo01 {
public static void main(String[] args) {
//大小为10的数组已经装满
int[]arr=new int[10];
for (int i = 0; i < 10; i++) {
arr[i]=i;
}
//现在想在末尾追加元素10
//先创建一个空间更大的数组
int[]newArr=new int[20];
//把原来的数据移进去
for (int i = 0; i < 10; i++) {
newArr[i]=i;}
//再在末尾加入元素
newArr[10]=10;
}
}
数组的扩容操作会涉及到新数组的开辟和数据的复制，时间复杂度是O(N)
删：删除静态数组的元素
情况一：删除末尾元素
把末尾元素标记成一个特殊值代表已删除
package com.wang.base.array;
public class Demo01 {
public static void main(String[] args) {
//大小为10的数组已经装满5个元素
int[]arr=new int[10];
for (int i = 0; i < 5; i++) {
arr[i]=i;
}
//删除末尾元素，暂时用-1逮捕元素已删除，在后面动态数组中会有更好解决方法
arr[4]=-1;
}
}
时间复杂度是O(1)
情况二：删除中间元素
涉及到数据搬移，把被删元素的后面元素都往前移动一位，保持连贯性
package com.wang.base.array;
public class Demo01 {
public static void main(String[] args) {
//大小为10的数组已经装满5个元素
int[]arr=new int[10];
for (int i = 0; i < 5; i++) {
arr[i]=i;
}
//想要删除arr【1】，需要把它后面的都向前移动一位
//注意要正着遍历数组中已有元素
for (int i = 1; i < 4; i++) {
arr[i]=arr[i+1];}
//最后一个元素为-1代表已经删除
arr[4]=-1;
}
}
时间复杂度是O(N)
查：给定索引，查询索引对应元素的值
时间复杂度O(1)
改：给定索引，修改索引对应元素的值
时间复杂度O(1)
动态数组的增删查改
动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩容缩容，并把增删改查操作进行了封装，让我们用起来更方便
package com.wang.base.array;
import java.util.ArrayList;
public class Demo02 {
public static void main(String[] args) {
//创建动态数组，不用显示指定大小，会根据实际存储的元素数量自动缩扩容
ArrayList<Integer>arr=new ArrayList<>();
for (int i = 0; i < 10; i++) {
//在末尾追加元素，时间复杂度O(1)
arr.add(i);
}
//在中间插入元素，时间复杂度O(N)
arr.add(2,666);//在索引为2的地方插入元素666
//在头部插入元素，时间复杂度O(1)
arr.add(0,-1);
//删除末尾元素，时间复杂度O(1)
arr.remove(arr.size()-1);
//删除中间元素，时间复杂度O(N)
arr.remove(2);//删除索引为2的元素
//根据索引查询元素，时间复杂度O(1)
int a= arr.get(0);//查询索引为0的元素
//根据索引修改元素，时间复杂度O(1)
arr.set(0,100);//把索引为0的元素修改成100
//根据元素值查找索引，时间复杂度O(N)
int index= arr.indexOf(666);//已知元素值是666，查找索引是多少
}
}
环形数组
可以在逻辑上把数组变成环形的
package com.wang.base.array;
public class Demo03 {
public static void main(String[] args) {
//长度为5的数组
int[]arr=new int[]{1,2,3,4,5};
int i=0;
//模拟环形数组，这个循环永远不会结束
while (i< arr.length){
System.out.println(arr[i]);
i=(i+1)% arr.length;
//当i到数组末尾元素时，i+1和arr.length取余数又会变成0，
// 即会回到数组头部，这样就在逻辑上形成了一个环形数组
}
}
}
start和end指针
环形数组的关键在于，维护了两个指针start和end，start指向第一个有效元素的索引，end指向最后一个有效元素的下一个位置索引。
这样在数组头部删除或添加元素，只需要移动start索引，而在数组尾部添加或删除元素，只需要移动end索引
当start，end移动超出数组边界（<0或>=arr.length）时，可以通过%让他们转一圈到数组头部或尾部继续工作，这样就实现了环形数组的效果
开闭区间
左开右闭：【start，end）区间包含数组元素
package com.wang.base.array;
public class Demo04 {
public class CycleArray<T>{
private T[]arr;
private int start;
private int end;
private int count;
private int size;
public CycleArray(){
this(1);
}
@SuppressWarnings("unchecked")
public CycleArray(int size){
this.size=size;
//因为Java不支持直接创建泛型数组，所以使用了类型转换
this.arr=(T[])new Object[size];
//start指向第一个有效元素的索引，是闭区间
this.start=0;
//end指向最后一个有效元素的下一个位置索引，是开区间
this.end=0;
this.count=0;
}
//自动扩缩容辅助函数
@SuppressWarnings("unchecked")
public void resize(int newSize){
//创建新的数组
T[] newArr=(T[])new Object[newSize];
//把旧的数组元素复制到新数组中
for (int i = 0; i < count; i++) {
newArr[i]=arr[(start+i)%size];
}
arr=newArr;
//重置start和end指针
start=0;
end=count;
size=newSize;
}
//在数组头部添加元素，时间复杂度O(1)
public void addFirst(T val){
//当数组满时，扩容为原来的两倍
if (isFull()){
resize(size*2);
}
//因为start是闭区间，所以先左移再赋值
start=(start-1+size)%size;
arr[start]=val;
count++;
}
//删除头部元素，时间复杂度O(1)
public void removeFirst(){
//防止数组是空的，没有元素，无法删减出现错误
if (isEmpty()){
throw new IllegalStateException("Array is empty");
}
//因为start是闭区间，所以先赋值再右移
arr[start]=null;
start=(start+1)%size;
count--;
//如果元素数量减少到原大小的四分之一，则减小数组大小为一半
if (count>0&&count==size/4){
resize(size/2);
}
}
//在数组尾部增加元素，时间复杂度O(1)
public void addLast(T val){
//防止数组是空的，没有元素，无法删减出现错误
if (isFull()){
resize(size*2);
}
//因为end是开区间，所以先赋值后右移
arr[end]=val;
end=(end+1)%size;
count++;
}
//删除数组尾部元素，时间复杂度O(1)
public void removeLast(){
//防止数组是空的，没有元素，无法删减出现错误
if (isEmpty()){
throw new IllegalStateException("Arry is empty");
}
//因为end是开区间，所以先左移，再赋值
end=(end-1+size)%size;
arr[end]=null;
count--;
//缩容
if (count>0&&count==size/4){
resize(size/2);
}
}
//获取数组头部元素，时间复杂度O(1)
public T getFirst(){
//防止数组是空的，没有元素，无法删减出现错误
if (isEmpty()){
throw new IllegalStateException("Arry is empty");
}
return arr[start];
}
//获取数组尾部元素，时间复杂度O(1)
public T getLast(){
//防止数组是空的，没有元素，无法删减出现错误
if (isEmpty()){
throw new IllegalStateException("Arry is empty");
}
//end是开区间，指向的是下一个元素的位置，所以要减一
return arr[(end-1+size)%size];
}
public boolean isFull(){
return count==size;
}
public int size(){
return count;
}
public boolean isEmpty(){
return count==0;
}
}
}